Reverse Linked List

Q: What about the recursive solution?

Recursively reverse head.next, then set head.next.next = head and head.next = null. It is elegant, but it uses O(n) stack space and can hit Python's default recursion limit of about 1000 on long lists. The iterative version is the safer default.

Q: What is the most common bug?

Overwriting curr.next before saving it, which cuts off the rest of the list. The second is returning head, which after the loop is the tail with next = null.

easyLinked list Must-do

You get the head of a singly linked list, where each node holds a value and a pointer to the next node. Reverse the list so that the last node becomes the first, and return the new head.

An empty list (head is null) should come back empty.

Examples

Example 1

Input: head = 4 -> 8 -> 15 -> 16

Output: 16 -> 15 -> 8 -> 4

Example 2

Input: head = 1 -> 2

Output: 2 -> 1

Explanation: With two nodes, the second node now points to the first, and the first points to nothing.

Hints

Approach

Reverse the pointers in place in one pass.

Start with prev = null and curr = head.
While curr is not null:
- save nxt = curr.next, because the next line destroys it;
- set curr.next = prev, flipping this link;
- move forward: prev = curr, curr = nxt.
When curr falls off the end, prev is the old tail, which is the new head.

The empty list and the single-node list need no special case: the loop runs zero or one time.

ComplexityTime O(n)Space O(1)

Python

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
 
class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        prev = None
        curr = head
        while curr:
            nxt = curr.next     # save the rest of the list
            curr.next = prev    # flip this node's pointer
            prev = curr         # step both pointers forward
            curr = nxt
        return prev             # prev is the old tail, now the head

Follow-up questions

Reverse only the nodes between positions left and right (Reverse Linked List II).
Reverse the list in groups of k nodes.

Frequently asked questions

Recursively reverse head.next, then set head.next.next = head and head.next = null. It is elegant, but it uses O(n) stack space and can hit Python's default recursion limit of about 1000 on long lists. The iterative version is the safer default.

Overwriting curr.next before saving it, which cuts off the rest of the list. The second is returning head, which after the loop is the tail with next = null.

They are a quick check that you can manage references without losing data, the same care you need when rewiring a chain of proxies, reordering middleware, or editing a doubly linked LRU list in a cache. Reversal is also a building block for harder list problems.

Problem statement