Reverse Linked List

You receive head, the first node of a singly linked list. Each node stores a value in val and a reference to the following node in next (the last node points to null).

Reverse the direction of every link so the former last node becomes the new first node, and return that new head. An empty list (head is null) stays empty.

In the examples a list is written as an array of its values from head to tail, e.g. [4,8,15] means 4 → 8 → 15.

Example 1

Example 2

Example 3

Constraints

• The number of nodes is between 0 and 5000.
• -5000 <= Node.val <= 5000

Pattern Path · Linked Lists · problem 68 of 169

Start simple

Copying the values into an array and rebuilding (or rewriting) the list backwards works in O(n) time but uses O(n) extra space.

The key idea

Reverse the links in place with three references. prev is the head of the part we have already reversed (initially empty, so null), cur is the first node not yet reversed (initially head), and a temporary nxt holds the rest of the original list.

At each step we first save nxt = cur.next, because the next line overwrites that link. Then cur.next = prev attaches cur to the front of the reversed part. Finally both pointers slide forward: prev = cur, cur = nxt.

The invariant is that prev always heads a correctly reversed list of all the nodes visited so far, and cur heads the untouched remainder. When cur becomes null the remainder is empty, so prev is the answer. Empty and one-node lists fall out naturally without special cases.

A recursive version (reverse the rest, then hook the current node onto its tail) is elegant too, but it uses O(n) call-stack space.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, cur = None, head
        while cur:
            nxt = cur.next       # remember the rest of the list
            cur.next = prev      # flip this link
            prev, cur = cur, nxt
        return prev

JavaScript

var reverseList = function(head) {
  let prev = null;
  let cur = head;
  while (cur) {
    const nxt = cur.next;  // remember the rest of the list
    cur.next = prev;       // flip this link
    prev = cur;
    cur = nxt;
  }
  return prev;
};

What the interviewer is checking

This is the fundamental pointer-manipulation exercise: the interviewer watches whether you update links in the right order without losing the rest of the list, and whether you can also explain the recursive variant.

Mistakes to avoid

• Overwriting cur.next before saving it, which cuts off the rest of the list.
• Returning the original head, which is now the tail.
• Forgetting that the old head must end up pointing to null, which creates a cycle.

Follow-ups to expect

• Can you do it recursively? (Reverse rest, then head.next.next = head.)
• Reverse only positions left..right. (Splice a reversed sublist back in.)
• Reverse the list in groups of k. (Reverse each block, reconnect ends.)

In real software

Undo histories, rebuilding a path from a chain of parent pointers, and in-place list manipulations inside memory allocators and kernels all rely on rewiring links safely in this order.

Practice next