This article does not have a corresponding language version

r: Reverse the entire singly linked list

First, let’s look at this set of linked lists

For example, suppose we have the following linked list:

head
 ↓
 1 → 2 → 3 → 4 → null

While keeping the positions of the nodes in the diagram unchanged, we need to reverse the directions of the edges between the nodes:

null ← 1 ← 2 ← 3 ← 4
                   ↑
                  head

It turns out that 1 It is a leaf node; there is no previous node. After reversal,1 It then becomes a leaf node, and its next Should point to null, and the new root node is 4。

From the new root node 4 Along next Let’s go. The traversal order is as follows: 4 → 3 → 2 → 1 → null. What changes are the pointers and the traversal order; the values within each node are not swapped.

What’s inside a node?

Let’s start by reviewing the concept of a node. Each node here has two fields:

  • .value: The value stored in this node.
  • .next: A reference to the next node.

Please note that when we refer to the “current node” later on, we are referring to the entire node, not just the value it contains.

We use c Represents the current node, i.e., “current."c.value It is its value,c.next It is the next node it points to.

When reversing a linked list,value Don’t move anything. We need to change the references between the nodes.

Declare three variables

Before we begin, let’s define three variables to store the previous node, the current node, and the original next node of the current node:

let p = null; // previous：前一个节点
let c = head; // current：当前节点

p At first, it equals null, because we’re starting from the root node, and there are no nodes before it.

c At first, it equals head, which is the head node of the linked list.

There’s one more n, which stands for “next.” It is saved each time the current node is processed during a round:

let n = c.next;

Why is it necessary to create a separate variable to store the next node?

Before changing the reference, save the nodes that follow it.

Let’s take another look at this set of linked lists:

1 → 2 → 3 → 4 → null

A node’s next A field can store only one reference at a time. There can be multiple nodes. next Point to the same node, but one next It cannot point to two nodes at the same time.

So, we need to change 1 If it points to something, you have to make it point to its original target 2 Replace the quotation marks.

But if you make the change directly, the following 2 → 3 → 4 What should we do? We can’t get through anymore. 1.next I found them.

So, let’s save it somewhere else first:

let n = c.next;

Once you’ve saved this, you can begin the process. c.next :

c.next = p;

In the first round,c It is a node 1，p Yes null. So once this step is complete, the result is:

c         n
↓         ↓
1 → null  2 → 3 → 4 → null

Look,c.value We didn’t move because it wouldn’t change;c.next It’s already been fixed. So this step is complete—it went very quickly.

Next, it’s time to prepare to process the next node.

Move the variable to the back

Now we need to move those variables; the order is as follows:

p = c;
c = n;

Why move it this way?

Because the current node has already been processed. Wait for the next round of node processing. 2 In this case, the “previous node” it points to is the node that was just processed. 1。

So let’s start by p = c, save the current node as the previous node for the next round.

Next, who should the current node be replaced with? It’s the next node that we saved earlier. n, so c = n。

Save this first. p = c, then move c. If you first c Change to n, then write p = c，p The node that is saved is not the one that was just processed.

After the first round:

p         c
↓         ↓
1 → null  2 → 3 → 4 → null

This takes us to the next node, where the next iteration begins.

The next node is the same.

Now c We’ve reached a turning point. 2。

First, save its original next node, which is the node 3：

let n = c.next;

Then modify the reference of the current node:

c.next = p;

At that moment p Pointing to a node 1, so this step is to make 2 Point to 1。

Move the variable again:

p = c;
c = n;

After the second round, it became:

p             c
↓             ↓
2 → 1 → null  3 → 4 → null

The same applies to the rest; continue processing from there:

第三轮结束：

p                 c
↓                 ↓
3 → 2 → 1 → null  4 → null

第四轮结束：

p                     c
↓                     ↓
4 → 3 → 2 → 1 → null  null

So our loop condition is: as long as c is not equal to null, I’ll just keep doing it.

etc. c become null, indicating that all nodes have been processed. At this point, p This points to the head node of the reversed linked list, so it ultimately returns p。

Complete Code

Here’s how it would be written in JavaScript. Assuming the input is head It is the root node; each node has value and next Field, the end of the linked list next Yes null：

function reverseList(head) {
  let p = null;
  let c = head;

  while (c !== null) {
    let n = c.next; // 先保存原来的下一个节点
    c.next = p;    // 把当前节点的指向反过来
    p = c;         // 当前节点成为下一轮的前一个节点
    c = n;         // 继续处理原来的下一个节点
  }

  return p;
}

Each round actually consists of just four steps:

  1. Save the next node.
  2. Modify the reference of the current node.
  3. Let p Points to the node that has just been processed.
  4. Let c Move to the next node to be processed.

No values were exchanged between nodes throughout the entire process; all changes were made to next. Since each node is processed only once, the time complexity is O(n); Using only these variables, the additional space complexity is O(1)。

If an empty linked list is passed in,c Right from the start, it was null, the loop will not execute; it will return immediately null. If there is only one node, the same node will be returned after one round of processing.