LeetCode 206 - Reverse Linked List

The problem asks us to reverse a singly linked list. A singly linked list is a sequence of nodes where each node stores a value and a pointer to the next node in the sequence. The input, head, represents the first node of the linked list.

leetcodeeasylinked-listrecursion

LeetCode Problem 206

Difficulty: 🟢 Easy
Topics: Linked List, Recursion

Solution

Problem Understanding

The problem asks us to reverse a singly linked list. A singly linked list is a sequence of nodes where each node stores a value and a pointer to the next node in the sequence. The input, head, represents the first node of the linked list. Our task is to rearrange the connections between the nodes so that the direction of the list is completely reversed.

For example, if the original list is:

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

after reversal, it should become:

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

The important detail is that we are not creating a new list of values. Instead, we are modifying the next pointers of the existing nodes so that every link points in the opposite direction.

The constraints tell us that the list can contain anywhere from 0 to 5000 nodes. This means the list may be empty, may contain only one node, or may contain several thousand nodes. Since the input size is relatively moderate, both iterative and recursive approaches are feasible. However, recursion introduces additional call stack usage, so the iterative approach is generally more space efficient.

Several edge cases are important:

  • The list may be empty (head = None)
  • The list may contain only one node
  • The list may contain two nodes, which is the smallest non-trivial reversal
  • The implementation must correctly reconnect pointers without losing access to the remaining nodes

A naive implementation can easily break the list if it overwrites a pointer before saving the next node reference.

Approaches

A brute-force approach would be to extract all node values into an array, reverse the array, and then rebuild the linked list or overwrite the node values in reverse order. This works because arrays allow direct indexed access, making reversal straightforward. However, this approach uses additional memory proportional to the size of the list, which is unnecessary because the problem only requires pointer manipulation.

A more optimal approach recognizes that reversing a linked list only requires changing the direction of each next pointer. At any point during traversal, we only need to know three things:

  • The current node being processed
  • The previous node, which should become the new next
  • The next node, so we do not lose access to the remainder of the list

By carefully updating these pointers in sequence, we can reverse the list in a single pass using constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Store node values or nodes in an array, then rebuild or overwrite
Optimal O(n) O(1) Reverse pointers in-place during traversal

Algorithm Walkthrough

Iterative Reversal Algorithm

  1. Initialize two pointers, previous and current.

previous starts as None because the new tail of the reversed list should point to nothing. current starts at the original head because we begin processing from the front of the list. 2. Traverse the linked list while current is not None.

This loop ensures every node is visited exactly once. 3. Save the next node before modifying pointers.

Since we are about to change current.next, we must first store the original next node in a temporary variable, usually called next_node. Otherwise, we would lose access to the remainder of the list. 4. Reverse the pointer direction.

Set:

current.next = previous

This changes the direction of the link so the current node now points backward instead of forward. 5. Move both pointers forward.

After reversing the connection:

  • Move previous to current
  • Move current to next_node

This advances the traversal while preserving the reversed portion of the list. 6. Continue until all nodes are processed.

When current becomes None, the traversal is complete and previous points to the new head of the reversed list. 7. Return previous.

Since previous ends on the final processed node, it represents the head of the reversed list.

Why it works

The key invariant is that before each iteration:

  • previous points to a correctly reversed portion of the list
  • current points to the next node that still needs processing

Each iteration removes one node from the unreversed portion and attaches it to the front of the reversed portion. Since every node is processed exactly once, the entire list becomes reversed by the end of the traversal.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        previous = None
        current = head
        
        while current:
            next_node = current.next
            current.next = previous
            
            previous = current
            current = next_node
        
        return previous

The implementation directly follows the iterative algorithm described earlier.

The variable previous tracks the head of the already reversed portion of the list. Initially, it is None because the reversed list is empty.

The variable current traverses the original list node by node. During each iteration, the algorithm first saves current.next into next_node. This step is critical because the next pointer is about to be overwritten.

The line:

current.next = previous

reverses the direction of the pointer.

After reversing the link, both traversal pointers move forward. previous expands the reversed list, while current advances to the next unprocessed node.

When traversal finishes, previous points to the new head of the reversed list, so it is returned.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var previous *ListNode = nil
    current := head

    for current != nil {
        nextNode := current.Next
        current.Next = previous

        previous = current
        current = nextNode
    }

    return previous
}

The Go implementation is nearly identical to the Python version in logic and structure.

Go uses nil instead of Python's None. Pointer manipulation is explicit because linked list nodes are referenced using *ListNode.

No special handling for integer overflow is necessary because the algorithm only manipulates pointers, not arithmetic values.

The iterative structure remains the same:

  • Save the next node
  • Reverse the pointer
  • Advance traversal pointers

Worked Examples

Example 1

Input:

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

Initial state:

Step previous current next_node List State
Start None 1 None 1 -> 2 -> 3 -> 4 -> 5

Iteration 1:

  • Save 2
  • Reverse 1.next to None
Step previous current next_node Reversed Portion
After Iteration 1 1 2 2 1 -> None

Iteration 2:

  • Save 3
  • Reverse 2.next to 1
Step previous current next_node Reversed Portion
After Iteration 2 2 3 3 2 -> 1 -> None

Iteration 3:

Step previous current next_node Reversed Portion
After Iteration 3 3 4 4 3 -> 2 -> 1 -> None

Iteration 4:

Step previous current next_node Reversed Portion
After Iteration 4 4 5 5 4 -> 3 -> 2 -> 1 -> None

Iteration 5:

Step previous current next_node Reversed Portion
After Iteration 5 5 None None 5 -> 4 -> 3 -> 2 -> 1 -> None

Final output:

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

Example 2

Input:

1 -> 2
Step previous current Result
Start None 1 Original list
Iteration 1 1 2 1 -> None
Iteration 2 2 None 2 -> 1 -> None

Final output:

2 -> 1

Example 3

Input:

[]

Initial state:

previous current
None None

Since current is already None, the loop never executes.

Final output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once
Space O(1) Only a few pointer variables are used

The algorithm performs a single traversal of the linked list. Every node undergoes one pointer reversal operation, so the runtime grows linearly with the number of nodes.

The space complexity is constant because no additional data structures proportional to the input size are allocated. Only three pointer variables are maintained regardless of list length.

Test Cases

# Helper functions for testing

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

def build_list(values):
    dummy = ListNode()
    current = dummy
    
    for value in values:
        current.next = ListNode(value)
        current = current.next
    
    return dummy.next

def linked_list_to_list(head):
    result = []
    
    while head:
        result.append(head.val)
        head = head.next
    
    return result

class Solution:
    def reverseList(self, head):
        previous = None
        current = head
        
        while current:
            next_node = current.next
            current.next = previous
            
            previous = current
            current = next_node
        
        return previous

solution = Solution()

# Example 1
head = build_list([1, 2, 3, 4, 5])
assert linked_list_to_list(solution.reverseList(head)) == [5, 4, 3, 2, 1]  # standard multi-node list

# Example 2
head = build_list([1, 2])
assert linked_list_to_list(solution.reverseList(head)) == [2, 1]  # two-node reversal

# Example 3
head = build_list([])
assert linked_list_to_list(solution.reverseList(head)) == []  # empty list

# Single node
head = build_list([42])
assert linked_list_to_list(solution.reverseList(head)) == [42]  # single-node edge case

# Repeated values
head = build_list([7, 7, 7])
assert linked_list_to_list(solution.reverseList(head)) == [7, 7, 7]  # duplicate values

# Negative numbers
head = build_list([-1, -2, -3])
assert linked_list_to_list(solution.reverseList(head)) == [-3, -2, -1]  # negative integers

# Long list
head = build_list(list(range(100)))
assert linked_list_to_list(solution.reverseList(head)) == list(range(99, -1, -1))  # larger input size
Test Why
[1,2,3,4,5] Validates standard multi-node reversal
[1,2] Smallest non-trivial linked list
[] Ensures empty input is handled correctly
[42] Verifies single-node lists remain unchanged
[7,7,7] Confirms logic does not depend on unique values
[-1,-2,-3] Ensures negative values work correctly
Large 100-node list Tests scalability and pointer consistency

Edge Cases

Empty List

An empty list means head is None. This case is important because attempting to access head.next without checking can cause runtime errors.

The implementation handles this naturally because the loop condition:

while current:

fails immediately when current is None. The function then returns previous, which is also None.

Single Node List

A list containing only one node is already reversed by definition. Some incorrect implementations accidentally disconnect the node or create cycles during pointer manipulation.

In this implementation, the single node's next pointer is reassigned to None, which it already is. The traversal then terminates correctly and returns the original node.

Losing the Remaining List

One of the most common bugs in linked list reversal is overwriting current.next before saving the reference to the remaining nodes.

For example, doing this incorrectly:

current.next = previous
current = current.next

would lose access to the unreversed portion of the list.

The implementation avoids this by first storing:

next_node = current.next

before changing any pointers. This guarantees that traversal can continue safely after reversal.