Card 02/ 08
Reverse a List Without Copying It or Walking to Its End
Fetching the last node again and again walks the list n times; turning each arrow round as you pass it walks it once.
Three references reverse a linked list in one walk, where the obvious approaches either walk to the end once per node or copy every value. The list P Q R has to come out as R Q P, with the same nodes and no new ones.
The first brute force takes the last node off and appends it to a new list, again and again. A singly linked list only knows its head, so finding the last node walks the whole list: n walks of up to n nodes is O(n²) time. The second copies the values into an array, reads it backwards and writes them back: O(n) time but O(n) extra memory. The repeated work in the first is the walk to the end, done once per node, though the nodes it passes are the ones about to be moved.
Walk to the endO(n²) time
Repeatedly walk from the head to the last node, detach it and append it to a new list. Every detach starts again from the head.
Three referencesO(n) time, O(1) space
Walk once. At each node save next, point the node back at prev, then step prev and curr forward.
Turning each arrow as the walk passes it removes both costs. The steps show every pointer move on P Q R, from an instrumented run, with the line just run and the list each reference heads.
Every pointer move while reversing P Q R
P: save next
after: next = curr.next
prev: null
curr: P → Q → R → null
next: Q → R → nullP: point back
after: curr.next = prev
prev: null
curr: P → null
next: Q → R → nullP: move prev
after: prev = curr
prev: P → null
curr: P → null
next: Q → R → nullP: move curr
after: curr = next
prev: P → null
curr: Q → R → null
next: Q → R → nullQ: save next
after: next = curr.next
prev: P → null
curr: Q → R → null
next: R → nullQ: point back
after: curr.next = prev
prev: P → null
curr: Q → P → null
next: R → nullQ: move prev
after: prev = curr
prev: Q → P → null
curr: Q → P → null
next: R → nullQ: move curr
after: curr = next
prev: Q → P → null
curr: R → null
next: R → nullR: save next
after: next = curr.next
prev: Q → P → null
curr: R → null
next: nullR: point back
after: curr.next = prev
prev: Q → P → null
curr: R → Q → P → null
next: nullR: move prev
after: prev = curr
prev: R → Q → P → null
curr: R → Q → P → null
next: nullR: move curr
after: curr = next
prev: R → Q → P → null
curr: null
next: nullTwelve moves, four per node, reverse three nodes, and at no point is a node unreachable: before curr.next is changed, next already holds the rest. The result is O(n) time, because each node is visited once, and O(1) extra space, because the three references are all that is added. prev ends on R, which is the new head, and the function returns it; returning the original head returns P, now the last node, with nothing after it.
← → move through sections and cards