LeetCode 206: Reverse Linked List

Problem Restatement

We are given the head of a singly linked list.

We need to reverse the list and return the new head.

Example:

1 -> 2 -> 3 -> 4 -> 5

becomes:

5 -> 4 -> 3 -> 2 -> 1

The official statement says: given the head of a singly linked list, reverse the list, and return the reversed list.

Input and Output

Typical node definition:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Example function shape:

def reverseList(head: ListNode) -> ListNode:
    ...

Examples

Example 1:

head = [1,2,3,4,5]

Result:

[5,4,3,2,1]

Example 2:

head = [1,2]

Result:

[2,1]

Example 3:

head = []

Result:

[]

Understanding Pointer Reversal

Suppose we have:

1 -> 2 -> 3

Each node points forward.

To reverse the list, we want:

1 <- 2 <- 3

The key operation is changing:

current.next

Instead of pointing forward, it should point backward.

The Main Difficulty

When we reverse a pointer, we risk losing the rest of the list.

Example:

1 -> 2 -> 3

If we immediately do:

2.next = 1

without saving 3, we lose access to the remaining nodes.

So before changing pointers, we must save the next node.

Key Insight

At every step we need three pointers:

Process:

prev <- current -> next_node

We reverse:

current.next = prev

Then move everything one step forward.

Algorithm

1. Initialize:
   • prev = None
   • current = head
2. While current exists:
   1. Save the next node.
   2. Reverse the pointer.
   3. Move prev forward.
   4. Move current forward.
3. Return prev.

At the end, prev becomes the new head.

Walkthrough

Initial list:

1 -> 2 -> 3 -> None

Start:

prev = None
current = 1

First iteration

Save next node:

next_node = 2

Reverse pointer:

1 -> None

Move pointers:

prev = 1
current = 2

Second iteration

Current structure:

1 <- 2 -> 3

Save:

next_node = 3

Reverse:

1 <- 2

Move forward:

prev = 2
current = 3

Final iteration

Reverse:

1 <- 2 <- 3

Now:

current = None

Loop ends.

Return:

prev

which points to node 3.

Correctness

The algorithm maintains the invariant that:

• prev points to the already reversed portion of the list.
• current points to the remaining unreversed portion.

Initially:

prev = None
current = head

So the reversed portion is empty.

At each iteration:

1. The algorithm saves the next node before modifying pointers.
2. It reverses the direction of current.next.
3. It extends the reversed portion by one node.
4. It advances to the next unreversed node.

No nodes are lost because the original next node is stored in next_node.

When the loop finishes, every pointer has been reversed, and prev points to the new head of the fully reversed list.

Therefore the algorithm correctly reverses the linked list.

Complexity

Iterative Implementation

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head

        while current:
            next_node = current.next

            current.next = prev

            prev = current
            current = next_node

        return prev

Code Explanation

Start with:

prev = None
current = head

prev represents the reversed part.

current represents the node being processed.

Save the next node before changing pointers:

next_node = current.next

Reverse the pointer:

current.next = prev

Move the pointers forward:

prev = current
current = next_node

At the end:

return prev

because prev points to the new head.

Recursive Solution

We can also reverse the list recursively.

Idea:

1. Reverse the rest of the list.
2. Attach the current node at the end.

Example:

1 -> 2 -> 3

Recursive calls reverse:

2 -> 3

into:

3 -> 2

Then connect:

3 -> 2 -> 1

Implementation:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return new_head

Recursive Code Explanation

Base case:

if not head or not head.next:
    return head

A list with zero or one node is already reversed.

Reverse the remaining list:

new_head = self.reverseList(head.next)

Suppose:

head = 1
head.next = 2

After recursion:

2 -> 1?

Now reverse the connection:

head.next.next = head

Break the old forward link:

head.next = None

Return the final head:

return new_head

Testing

def build_list(values):
    dummy = ListNode(0)
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

def run_tests():
    s = Solution()

    head = build_list([1,2,3,4,5])
    assert to_list(s.reverseList(head)) == [5,4,3,2,1]

    head = build_list([1,2])
    assert to_list(s.reverseList(head)) == [2,1]

    head = build_list([1])
    assert to_list(s.reverseList(head)) == [1]

    head = build_list([])
    assert to_list(s.reverseList(head)) == []

    print("all tests passed")

run_tests()