Reverse Linked List (LeetCode 206)

The problem

You get the head of a singly linked list. Reverse the list so the last node becomes the first, and return the new head. Each node has a val and a next pointer.

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

Every arrow now points the other way, so the old tail 5 is the new head.

How to think about it

Start with brute force. Walk the list, push every value into a Python list, then walk again and write the values back in reverse order (or build fresh nodes). That is O(n) time but O(n) extra space, and an interviewer will immediately ask you to do it without the array.

The key insight: you only need to change the arrows, not move the nodes. Each node’s next should point to the node before it. You can do that in one pass if you always know two things: the node you are on and the node you just left. The catch is that the moment you overwrite cur.next, you lose your only link to the rest of the list. So save the rest before you flip.

Three handles are enough. prev is the reversed part built so far (it starts as None, which becomes the new tail’s next). cur is the node being flipped. The saved next lets you keep walking. When cur falls off the end, prev is sitting on the old tail, which is the new head.

Which pattern is this? Linked-list in-place reversal. The tell is “reverse”, “in place” or “O(1) extra space” on a linked list. This three-pointer flip is the building block for sub-range reversal, k-group reversal and palindrome checks.

Approach

1. Set prev = None.
2. While head is not None:
   • point head.next back at prev,
   • move prev forward to head,
   • move head forward to the node that used to follow it.
3. Return prev, the new head.

Python’s tuple assignment evaluates the whole right-hand side first, so all three updates happen in one line using the old values. That is why the next node is not lost.

Solution

def reverse_list(head):
    prev = None                                     # reversed part so far
    while head:
        # RHS is evaluated first: (prev, head, head.next) are the OLD values
        head.next, prev, head = prev, head, head.next
    return prev                                     # old tail = new head
# reverse_list([1,2,3,4,5]) -> [5,4,3,2,1]

If the one-liner feels too clever in an interview, write it out with nxt = head.next first. The logic is identical.

Dry run

On 1 -> 2 -> 3 -> 4 -> 5, after each loop iteration:

head is None, so the loop stops and prev (node 5) is returned.

Complexity

• Time: O(n). Each node is visited once and gets one pointer change.
• Space: O(1). Only prev and head are stored, whatever the list length. The recursive version is O(n) space because of the call stack.

Edge cases and pitfalls

• Empty list (head = None): the loop never runs and None is returned.
• Single node: one iteration sets its next to None and returns it.
• Losing the rest of the list. Writing head.next = prev on its own line before saving head.next cuts the list off. Save first, then flip.
• Reordering the tuple assignment. Targets on the left are assigned left to right, so prev, head, head.next = head, head.next, prev moves head first and then writes to the wrong node’s next (it crashes on None at the end). Keep head.next first on the left, or use an explicit nxt variable.
• Returning head instead of prev. At the end head is None.

Related problems

• Reverse Linked List II (LeetCode 92): reverse only positions left..right and splice it back.
• Reverse Nodes in k-Group (LeetCode 25): run this same flip on every block of k nodes.
• Palindrome Linked List (LeetCode 234): find the middle, reverse the second half, compare.