AlgoVerse

Reversing a linked list

Turn every link of the list around one by one with three pointers, prev, cur and nxt; in one pass with no extra memory.

Walk the list from the start and turn each node's link back to the previous node. Three pointers are needed:

Read the full explanation ↓
Input:
n=5PDF export

1 → 2 → 3 → 4 → 5 becomes 5 → 4 → 3 → 2 → 1.

  1. class Node:
  2. def __init__(self, val):
  3. self.val = val
  4. self.next = None
  7. def reverse_list(items):
  8. head = None
  9. for x in reversed(items):
  10. node = Node(x)
  11. node.next = head
  12. head = node
  13. # prev: the part already reversed; cur: the part still to do.
  14. prev, cur = None, head
  15. while cur is not None:
  16. nxt = cur.next
  17. cur.next = prev
  18. prev = cur
  19. cur = nxt
  20. head = prev
  21. out = []
  22. while head is not None:
  23. out.append(head.val)
  24. head = head.next
  25. return out

Invariant: prev always heads the reversed part and cur the part left; no node gets lost because nxt is saved before the link turns.

Start

prevnull
curnull

Local variables

Orange = changed in this step

items list

12345

Call stack

  1. reverse_list()line 7
Step 1 of 84
Black = flip · Orange = key stepbuilt: 0/1 · flip: 0/5 · advance: 0/5 · done: 0/1
    Explanation

    The idea

    Walk the list from the start and turn each node's link back to the previous node. Three pointers are needed:

    • prev: the head of the part reversed so far,
    • cur: the node whose link turns now,
    • nxt: the next node, which must be saved before the link turns, or the rest of the list is lost.

    At the end prev heads the reversed list.

    Cost

    One pass and a few pointers: O(n) time and O(1) memory. No node is copied or moved.

    What to watch in the trace

    • Two lists are drawn: from prev (the reversed part) and from cur (the part left); each step moves one node from the second to the first.