Reverse Linked List

Reverse Linked List

Problem Description
Reversing a linked list is a very classic interview question. The task is to reverse the order of all nodes in a singly linked list and return the head node of the reversed list. For example, given the linked list 1 -> 2 -> 3 -> 4 -> 5, after reversal it should become 5 -> 4 -> 3 -> 2 -> 1. This problem tests the understanding of the linked list data structure and proficiency in pointer (reference) manipulation.

Solution Process

We will use an iterative approach to solve this problem, which is one of the most intuitive and efficient methods. The entire process can be understood as traversing the linked list while "bending" the direction of each node's pointer to the opposite side.

Core Idea
We need three pointers to work together:

  1. prev: Points to the previous node of the current node (initialized as null, because after reversal, the original head node will become the tail node, and its next should point to null).
  2. curr: Points to the node currently being processed.
  3. next: Temporarily saves the next node of the current node, preventing the linked list from breaking and losing subsequent nodes after modifying the pointer of curr.next.

Step-by-Step Breakdown

Suppose we have a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null. Our goal is to reverse it to 5 -> 4 -> 3 -> 2 -> 1 -> null.

  • Step Zero: Initialization

    • Before starting the traversal, we set the prev pointer to null and the curr pointer to the head node of the linked list (i.e., node 1).
    • Current state: prev = null, curr = 1.
    • Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null

  • Step One: Process the first node (node 1)

    1. Save the next node: First, we need a temporary pointer next to save the next node of curr, which is node 2. next = curr.next (next = 2). This step is crucial because in the next step we will modify curr.next. If we don't save it beforehand, we will lose the reference to node 2.
    2. Reverse the pointer: Then, we make the next pointer of the current node curr (node 1) point to its previous node prev (which is null at this moment). Execute curr.next = prev. Now, node 1 points to null. The linked list becomes 1 -> null, while the part 2 -> 3 -> 4 -> 5 is saved by the next pointer.
    3. Move pointers forward: Now, we have completed the reversal of node 1. Next, we need to process node 2. We move the prev pointer to the position of curr (i.e., node 1), and move the curr pointer to the position of next (i.e., node 2). Execute prev = curr (prev = 1), then curr = next (curr = 2).
    • Current state: prev = 1, curr = 2, next = 2.
    • Current reversed part: 1 -> null
    • Remaining linked list: 2 -> 3 -> 4 -> 5 -> null

  • Step Two: Process the second node (node 2)

    1. Save the next node: next = curr.next (next = 3).
    2. Reverse the pointer: curr.next = prev. Make the next of node 2 point to node 1. Now the linked list structure is 2 -> 1 -> null.
    3. Move pointers forward: prev = curr (prev = 2), curr = next (curr = 3).
    • Current state: prev = 2, curr = 3, next = 3.
    • Current reversed part: 2 -> 1 -> null
    • Remaining linked list: 3 -> 4 -> 5 -> null

  • Step Three: Process the third node (node 3)

    1. Save the next node: next = curr.next (next = 4).
    2. Reverse the pointer: curr.next = prev. Make the next of node 3 point to node 2. Now the linked list structure is 3 -> 2 -> 1 -> null.
    3. Move pointers forward: prev = curr (prev = 3), curr = next (curr = 4).
    • Current state: prev = 3, curr = 4, next = 4.
    • Current reversed part: 3 -> 2 -> 1 -> null
    • Remaining linked list: 4 -> 5 -> null

  • Steps Four and Five: And so on...

    • We repeat this process until the last node (node 5) is processed.

  • Step Six: Process the last node (node 5) and termination condition

    1. At this point, curr points to node 5, and prev points to node 4. The linked list state is 4 -> 3 -> 2 -> 1 -> null, remaining 5 -> null.
    2. Save the next node: next = curr.next (next = null).
    3. Reverse the pointer: curr.next = prev. Make the next of node 5 point to node 4. The linked list structure becomes 5 -> 4 -> 3 -> 2 -> 1 -> null.
    4. Move pointers forward: prev = curr (prev = 5), curr = next (curr = null).
    • Now, the curr pointer is null, which means we have traversed all nodes of the original linked list.

  • Return Result

    • After the loop ends, the prev pointer points to the head node of the new reversed linked list, which is the tail node of the original list (node 5). Therefore, we finally return prev.

Summary
The core of this iterative algorithm lies in performing the same four operations in each step:

  1. Temporarily save the next node of the current node (next = curr.next).
  2. Make the current node's pointer point to the previous node (reversal operation, curr.next = prev).
  3. Move the prev pointer forward (prev = curr).
  4. Move the curr pointer forward (curr = next).

The loop terminates when the curr pointer becomes null. The time complexity of the entire algorithm is O(n), where n is the length of the linked list, because we only traverse the list once. The space complexity is O(1), as we only use a few fixed pointers and no additional data structures.