LeetCode 206 · Linked List

Reverse Linked List, explained with a picture

Recoupling a train backwards.

EasyLinked List
▶ Watch it step by step

The problem

Given the head of a singly linked list, reverse the list and return the new head.

Input:  1 → 2 → 3 → 4
Output: 4 → 3 → 2 → 1

Picture it

A linked list is like a train: each coach holds a value and a coupling to the next coach. The only way in is the first coach (the head). To reverse it, we walk along with three markers: prev (the part already reversed), curr (the coach we’re fixing) and nxt (the rest of the train, remembered so we don’t lose it). For each coach we flip its coupling to point backwards.

How to recognise it

  • The input is a singly linked list: each node knows only the next node, so you cannot step backwards.
  • You must change the direction of the links, not just read values in reverse.
  • The answer is a new head, which was the old tail.
  • The follow-up asks for O(1) extra space: no array of nodes and no recursion stack.
  • Reversing a list (or part of one) is a building block for harder problems such as Reorder List and Reverse Nodes in k-Group, so it is worth knowing by heart.

Start with brute force

Walk the list once and store every node in a Python list. Then use the indices, which can go backwards, to point each node at the one before it.

def reverse_brute(head):
    nodes = []
    while head:
        nodes.append(head)
        head = head.next
    if not nodes:
        return None
    for i in range(len(nodes) - 1, 0, -1):
        nodes[i].next = nodes[i - 1]
    nodes[0].next = None
    return nodes[-1]

Time is O(n) and extra space is O(n). With LeetCode's limit of 5,000 nodes this is not too slow; the problem is memory. It stores a reference to every node only because a singly linked list cannot be walked backwards, and the follow-up asks you to avoid exactly that.

From brute force to the idea

  1. Find the waste. The array exists only so that each node can reach "the node before me". But while you walk forwards, the node before is the one you just left. You only ever need that one.
  2. Keep three references. prev is the head of the part already reversed (it starts as None), curr is the node being fixed, and nxt remembers the rest of the list.
  3. Save before you cut. nxt = curr.next must come first. Once curr.next points backwards, the rest of the list is unreachable unless you saved it.
  4. Flip one link. curr.next = prev turns the arrow around. The very first node gets None, so it becomes the new tail.
  5. Move both forward. prev = curr and curr = nxt. When curr falls off the end, prev is the old tail, now the head.

This is the key idea: save the next node, point the current node back, then move both pointers one step forward.

The key idea

Remember next, point curr back at prev, then move both forward. O(n) time, O(1) extra space.

Python solution

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n): one pass to collect, one to relinkO(n): a reference to every node
Three pointers (shown code)O(n): each node is visited once and its link changed onceO(1): only prev, curr and nxt

Edge cases

  • Empty list (head is None): the loop never runs and the code returns None.
  • One node: its next is set to None (it already was) and it is returned.
  • Two nodes (1 → 2): returns 2 → 1, and node 1's next is now None, so there is no cycle.
  • Long list: the loop is iterative, so 5,000 or even 10^6 nodes are fine. A recursive version would raise RecursionError at around 1,000 nodes, Python's default recursion limit.
  • Old head reference: after the call, the caller's old head variable points to the new tail, a list of one node. Always use the returned head.

Common mistakes

  • Writing curr.next = prev before saving curr.next, which loses the rest of the list after one step.
  • Returning curr instead of prev. At the end curr is None.
  • Forgetting that the old head must end with None. Starting prev at None handles this; starting it at head creates a cycle.
  • Swapping values instead of links. It gives the right printout but is not what the problem asks, and it needs O(n) space or O(n²) time to reach the back.
Your turn: reverse only a section

Given the head and two positions left ≤ right (1-based), reverse only the nodes from position left to right and return the head. For 1 → 2 → 3 → 4 → 5 with left 2 and right 4 the answer is 1 → 4 → 3 → 2 → 5. Describe your approach, then write it if you like.

Compare with our answer

Walk to the node just before the section, using a dummy node in case the section starts at the head. Reverse exactly right − left + 1 nodes with the same three-pointer loop. Afterwards prev is the section's new first node and curr is the first node after it; the old first node of the section is now its last, so link it to curr.

def reverse_between(head, left, right):
    dummy = Node(0, head)
    before = dummy
    for _ in range(left - 1):
        before = before.next
    prev, curr = None, before.next
    for _ in range(right - left + 1):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    tail = before.next        # first node of the section, now its last
    tail.next = curr
    before.next = prev
    return dummy.next

Time O(n), space O(1).

A strong answer mentions: a dummy node so left = 1 needs no special case, counting the nodes to reverse instead of running to the end, and reconnecting both ends of the reversed section.

Check what stuck

1. A list of 10^6 nodes must be reversed in place, using O(1) extra memory. Which approach fits best?

2. Why does the shown code use O(1) extra space for a list of any length?

3. A learner drops nxt = curr.next and writes curr = curr.next as the last line of the loop. What does it return for 1 → 2 → 3?

Score 60% or more and the lesson is marked complete.