Skip to content
GKgkml.dev
← Problem set
#206EasyLinked lists

Reverse Linked List

The tell: Reverse pointer direction in place, with O(1) extra space.

How you get there

  1. 1Carry three references: previous, current, and the next node.
  2. 2Save next before overwriting current.next, or the rest of the list is lost.
  3. 3Advance all three and repeat; previous ends up as the new head.

Solution

Python
def reverse_list(head):
    prev = None
    while head:
        nxt = head.next      # save before overwriting
        head.next = prev
        prev = head
        head = nxt
    return prev
Time
O(n)
Space
O(1)

What goes wrong

Overwriting head.next before saving it strands the remainder of the list.

Test yourself on DSANext: Remove Nth Node From End of List →