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

Canonical input 1 -> 2 -> 3 -> 4 -> 5 reverses to 5 -> 4 -> 3 -> 2 -> 1 -> null.

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;

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.