Linked Structures

Reverse a Linked List

Reverse a singly linked list by flipping every next_idx pointer. A recursive walk visits each node once and records its predecessor; the head becomes the original tail.

Algorithm

Basic Implementation

basic.sql 
.mode list
.headers off
CREATE TABLE node(idx INTEGER PRIMARY KEY, val INTEGER, next_idx INTEGER);
INSERT INTO node(idx, val, next_idx) VALUES
  (0, 1, 1),
  (1, 2, 2),
  (2, 3, 3),
  (3, 4, 4),
  (4, 5, NULL);

CREATE TABLE reversed(idx INTEGER PRIMARY KEY, val INTEGER, next_idx INTEGER);
WITH RECURSIVE flip(cur, prev) AS (
  SELECT 0, NULL
  UNION ALL
  SELECT (SELECT next_idx FROM node WHERE idx = flip.cur), flip.cur
  FROM flip
  WHERE flip.cur IS NOT NULL
)
INSERT INTO reversed(idx, val, next_idx)
SELECT n.idx, n.val, flip.prev
FROM node n JOIN flip ON flip.cur = n.idx;

WITH RECURSIVE head(idx) AS (
  SELECT idx FROM reversed WHERE idx NOT IN (
    SELECT next_idx FROM reversed WHERE next_idx IS NOT NULL
  )
),
walk(idx, line) AS (
  SELECT reversed.idx, CAST(reversed.val AS TEXT) || ' -> '
  FROM reversed JOIN head ON head.idx = reversed.idx
  UNION ALL
  SELECT reversed.idx, walk.line || CAST(reversed.val AS TEXT) || ' -> '
  FROM walk JOIN reversed
    ON reversed.idx = (SELECT next_idx FROM reversed WHERE idx = walk.idx)
  WHERE (SELECT next_idx FROM reversed WHERE idx = walk.idx) IS NOT NULL
)
SELECT line || 'null' FROM walk
ORDER BY LENGTH(line) DESC LIMIT 1;

The three-pointer loop saves the forward link, flips one next pointer, then advances prev and cursor.

Step 1 - Save the first forward link

prev starts at null, cursor is node(1), and nxt saves node(2).

Initial 1 -> 2 -> 3 -> 4 -> 5 chain with prev, cursor, and nxt named.prevcursornxtnullnode(1)node(2)node(3)node(4)node(5)

Step 2 - Flip node(1)

Set node(1).next to prev, making the reversed prefix 1 -> null.

After the first flip, prev points at node(1) and cursor advances to node(2).prevcursornode(1)nullnode(2)node(3)node(4)node(5)

Step 3 - Reversed prefix reaches 3

After three flips, the prefix is 3 -> 2 -> 1 -> null and cursor is node(4).

Middle of the reverse: prefix 3 -> 2 -> 1, suffix 4 -> 5.prevcursornode(3)node(2)node(1)nullnode(4)node(5)

Step 4 - Done

When cursor reaches null, prev is the new head: 5 -> 4 -> 3 -> 2 -> 1 -> null.

Final reversed list.headnode(5)node(4)node(3)node(2)node(1)null

Complexity

  • Time: O(n)
  • Space: O(n) for the reversed table holding the rewritten pointers

Implementation notes

  • SQL: the input list is staged in node(idx, val, next_idx) with the original ordering. A WITH RECURSIVE flip(cur, prev) CTE walks forward through next_idx, producing one row per node that pairs the node's own index with the index that came before it.
  • The INSERT INTO reversed projection joins each node to its flip row so the new next_idx is the original predecessor — exactly what a prev/curr/next imperative loop would write back. The original head's prev is NULL, so its reversed next_idx is the null sentinel.
  • The printing walk finds the new head as the index that is no row's next_idx in reversed, then chains forward through the reversed pointers to produce 5 -> 4 -> 3 -> 2 -> 1 -> null.
pointer flip For each node, set its new `next` to the node that arrived just before it in the original walk. The original head's new `next` is `null`.
head swap After every node is flipped, the original tail is the new head.