Reverse Linked List

Difficulty: Easy Source: NeetCode

Problem

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

Example 1: Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2: Input: head = [1,2] Output: [2,1]

Constraints:

• The number of nodes in the list is in the range [0, 5000]
• -5000 <= Node.val <= 5000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Traversal — walking a linked list node by node using .next
• Pointer Manipulation — re-assigning .next references to change list structure

1. Brute Force / Naive Approach

Intuition

The simplest idea is to not think about pointers at all. Just walk the list, collect all the values into a Python list, reverse that list, then rebuild a brand new linked list. It wastes memory but it’s easy to reason about and a great starting point.

Algorithm

1. Walk the original list and collect all node values into a Python list.
2. Reverse the Python list.
3. Build a new linked list from the reversed values and return its head.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

# Brute force: collect values, rebuild reversed
def reverseList_brute(head):
    values = []
    cur = head
    while cur:
        values.append(cur.val)
        cur = cur.next

    values.reverse()

    dummy = ListNode(0)
    cur = dummy
    for v in values:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Input:  ", end=""); print_list(head)
result = reverseList_brute(head)
print("Output: ", end=""); print_list(result)  # 5 -> 4 -> 3 -> 2 -> 1

head2 = build_list([1, 2])
result2 = reverseList_brute(head2)
print("Output: ", end=""); print_list(result2)  # 2 -> 1

head3 = build_list([])
result3 = reverseList_brute(head3)
print("Output: ", end=""); print_list(result3)  # None

Complexity

• Time: O(n) — two passes over the list
• Space: O(n) — storing all values in a Python list

2. Iterative In-Place (Optimal)

Intuition

Instead of collecting values, we can flip the .next pointers directly as we walk the list. We keep track of two pointers: prev (starts as None) and curr (starts at head). At each step, we save curr.next, point curr.next back to prev, then advance both pointers forward. When curr falls off the end, prev is the new head.

Initial:  None <- 1 -> 2 -> 3 -> 4 -> 5
After 1:  None <- 1 <- 2    3 -> 4 -> 5
After 2:  None <- 1 <- 2 <- 3    4 -> 5
...
Final:    None <- 1 <- 2 <- 3 <- 4 <- 5

Algorithm

1. Initialize prev = None and curr = head.
2. While curr is not None: a. Save next_node = curr.next. b. Point curr.next = prev (reverse the arrow). c. Move prev = curr. d. Move curr = next_node.
3. Return prev as the new head.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next  # save next before we overwrite it
        curr.next = prev       # flip the pointer
        prev = curr            # advance prev
        curr = next_node       # advance curr
    return prev  # prev is now the new head

# Test cases
head = build_list([1, 2, 3, 4, 5])
print("Input:  ", end=""); print_list(head)
result = reverseList(head)
print("Output: ", end=""); print_list(result)  # 5 -> 4 -> 3 -> 2 -> 1

head2 = build_list([1, 2])
print("Output: ", end=""); print_list(reverseList(head2))  # 2 -> 1

print("Output: ", end=""); print_list(reverseList(None))   # None

Complexity

• Time: O(n) — single pass
• Space: O(1) — only two pointer variables

3. Recursive Approach

Intuition

Recursion is elegant here: to reverse a list, reverse everything after the head, then make the second node point back to the head and detach the head’s .next. The base case is an empty list or single node — that’s already reversed.

Think of it this way: if we call reverseList([2,3,4,5]) and it gives us back 5->4->3->2, then 2.next still points to 3. We want 3 to point back to 1… actually we want head.next.next = head and head.next = None.

Algorithm

1. Base case: if head is None or head.next is None, return head.
2. Recurse on head.next — this reverses the rest and returns the new head.
3. Set head.next.next = head (make the node after head point back to head).
4. Set head.next = None (detach head from the old chain).
5. Return the new head from step 2.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def reverseList_recursive(head):
    # Base case: empty list or single node
    if not head or not head.next:
        return head

    # Reverse the rest of the list
    new_head = reverseList_recursive(head.next)

    # head.next is now the tail of the reversed sublist
    # Make it point back to head
    head.next.next = head
    head.next = None  # head becomes the new tail

    return new_head

# Test cases
head = build_list([1, 2, 3, 4, 5])
result = reverseList_recursive(head)
print("Output: ", end=""); print_list(result)  # 5 -> 4 -> 3 -> 2 -> 1

head2 = build_list([1, 2])
print("Output: ", end=""); print_list(reverseList_recursive(head2))  # 2 -> 1

print("Output: ", end=""); print_list(reverseList_recursive(None))   # None

Complexity

• Time: O(n) — visits every node once
• Space: O(n) — call stack depth equals list length

Common Pitfalls

Forgetting to save curr.next before overwriting it. Once you do curr.next = prev, you’ve lost your reference to the rest of the list. Always save next_node = curr.next first.

Returning curr instead of prev. When the loop ends, curr is None and prev is the last node you processed — which is the new head. Returning curr gives back None.

Forgetting head.next = None in the recursive approach. Without this, the original head still points forward, creating a cycle in your result.