Reverse Linked List

The problem

You are given head, the first node of a singly linked list. Each node holds a value, val, and a link, next, to the node after it, and the last node's next is null. Return the first node of the same list in reverse order. An empty list is given as null, and its reverse is null too. The checker follows next from the node you return and compares the values, so you may reuse the given nodes or build new ones.

What to write

type ListNode = { val: number; next: ListNode | null };

function solve(head: ListNode | null): ListNode | null

Input
head = {"val":1,"next":{"val":2,"next":null}}

Output
{"val":2,"next":{"val":1,"next":null}}

Input
head = null

Output
null

Constraints

0–500 acyclic nodes; integer val; next is a node or null.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A node only knows the node after it, so you can walk the list forward but never backward. The list may be empty, given as null, or hold a single node. Both of those are already their own reverse.

2. Hint 2: Ask a smaller question

   Draw 1 → 2 → 3 on paper and look only at the node 2. Where must its link point in the reversed list? If you change that link right away, how will you still reach the node 3?

3. Hint 3: Name the pattern

   No node has to move and no value has to change. Each node only needs its link turned around, so that it points at the node before it. Changing the links of existing nodes is linked list pointer rewiring. The signal: the answer is the same nodes in a new order. Read the lesson on linked list pointer rewiring.

4. Hint 4: State the invariant

   The list is always in two parts. The reversed part holds the nodes you have visited, with their links already turned. The rest is still in its original order. You hold the first node of each part, so no node is ever out of reach.

5. Hint 5: Sketch the pseudocode

   reversed = null. While head is not null: save the node after head; point the next of head at reversed; reversed = head; head = the saved node. Return reversed.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Save the next pointer before changing it. Point the current node backward, then advance the previous and current pointers.

The slow way

Walk the list and collect every value in an array. Then walk the list again and write the values back in reverse order. The answer is right, but the array keeps a copy of all n values, when the nodes already hold everything the answer needs.

The insight

Reversing a list does not move any node. Only the links change direction: a node that pointed at the node after it must point at the node before it. If you remember the node before as you walk, you can turn each link the moment you pass it.

Step by step

1. Start with an empty reversed part. The reversed part is the piece of the list whose links are already turned. It starts empty, written as null. Null is also the link the first node needs, because that node ends up last.
2. Save the next node before this node's link is changed. The link is your only way to reach the rest of the list. Once the link points somewhere else, the next node can be found only if you saved that node first.
3. Turn this node's link around to point at the reversed part. In the reversed list a node is followed by the node that used to come before it, and that node is the first one of the reversed part.
4. This node now leads the reversed part; step to the saved node. The node has joined the front of the reversed part, so the reversed part now starts with this node. The saved node is the first one whose link is still unturned.
5. Every node is turned, so the reversed part is the answer. The loop ends when no node is left to visit. The reversed part then starts with the old last node and holds every node. For an empty list the reversed part is still null, which is the right answer.

The same numbered steps are the comments in each solution.

function solve(head) {
  // 1. Start with an empty reversed part
  let prev = null;
  while (head) {
    // 2. Save the next node before this node's link is changed
    const next = head.next;
    // 3. Turn this node's link around to point at the reversed part
    head.next = prev;
    // 4. This node now leads the reversed part; step to the saved node
    prev = head;
    head = next;
  }
  // 5. Every node is turned, so the reversed part is the answer
  return prev;
}

type ListNode = { val: number; next: ListNode | null };
function solve(head: ListNode | null): ListNode | null {
  // 1. Start with an empty reversed part
  let prev = null;
  while (head) {
    // 2. Save the next node before this node's link is changed
    const next = head.next;
    // 3. Turn this node's link around to point at the reversed part
    head.next = prev;
    // 4. This node now leads the reversed part; step to the saved node
    prev = head;
    head = next;
  }
  // 5. Every node is turned, so the reversed part is the answer
  return prev;
}

def solve(head):
    # 1. Start with an empty reversed part
    prev = None
    while head:
        # 2. Save the next node before this node's link is changed
        after = head.next
        # 3. Turn this node's link around to point at the reversed part
        head.next = prev
        # 4. This node now leads the reversed part; step to the saved node
        prev = head
        head = after
    # 5. Every node is turned, so the reversed part is the answer
    return prev

Example 1, traced

Input
head = {"val":1,"next":{"val":2,"next":null}}

Output
{"val":2,"next":{"val":1,"next":null}}

Why it works

Before every round, the reversed part holds the visited nodes in reverse order, and the rest holds the other nodes in their original order. One round moves the first node of the rest to the front of the reversed part. When the rest is empty, the reversed part is the whole list, reversed.

Time and space

Time O(n), extra space O(1). The loop visits each node once and does a fixed amount of work for it, so the time is O(n) for n nodes. It creates no nodes and keeps three references however long the list is, so the extra space is O(1).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Save the next node before you change the link. If you change the link first and then follow it, you land in the reversed part: the loop ends after one node and the answer is that single node.
• Return the front of the reversed part, not the node you were given. That node is now the last one and its link is null, so returning it gives a list of one node.
• Loop until the current node is null, not until its link is null. Stopping one node early leaves the last node out of the answer, and a single node comes back as an empty list.

Pattern

Linked list pointer rewiring.

Keep going