How do the pointers work in the Linked List?

Question

I've just learned the Linked List reverse function but don't understand it not enough I think. The first, second, temp variables are Pointers right? And they are going to change within the while loop, am i right? What I badly understand how does it reverse it. I went through it multiple times with the debugger but still dont understand how the Pointers work here and how it changes its next value. Here is the Linked List:

class LinkedList {
        constructor(value) {
            this.head = {
                value: value,
                next: null
            };
            this.tail = this.head;
            this.length = 1;
        }
        append(value) {
          const newNode = {
            value: value,
            next: null
          }
          this.tail.next = newNode;
          this.tail = newNode;
          this.length++;
          return this;
        }
        printList() {
          const array = [];
          let currentNode = this.head;
          while(currentNode !== null){
              array.push(currentNode.value)
              currentNode = currentNode.next
          }
          return array;
        }
        reverse() {
          if (!this.head.next) {
            return this.head;
          }
          var first = this.head; // 1
          this.tail = this.head; 
          var second = first.next; // 2
          while(second) { // Runs 2 times
            const temp = second.next; // 3
            second.next = first; // 3 => 1
            first = second; // 1 => 2
            second = temp;  2 => 3
          }
      
          this.head.next = null;
          this.head = first;
          return this;
        }
    }
    
    let myLinkedList = new LinkedList(1);
    myLinkedList.append(2)
    myLinkedList.append(3)
    myLinkedList.reverse()

I would highly appreciate if you could explain it to me step by step. Thank you very much in advance, ~ Lukas

Answer 1

I would highly appreciate if you could explain it to me step by step

Let's start with the state as it is after the values 1, 2 and 3 have been inserted:

 head                             tail
  ↓                                ↓
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │ next: ——————→ │ next:null│
└──────────┘    └──────────┘    └──────────┘

When the while loop begins, we have introduced a few more references. Note how second got there via first.next, i.e. it references the same object as the next reference in the first object. Also, this.tail is set to its final value, so we don't have to think about that any more:

 first
 head
 tail            second
  ↓               ↓
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │ next: ——————→ │ next:null│
└──────────┘    └──────────┘    └──────────┘

Now let's picture the effect of each assignment in the while loop:

First iteration:

const temp = second.next; initialises a new reference, which equals the next reference in the object that is referenced by second:

 first
 head
 tail            second          temp
  ↓               ↓               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │ next: ——————→ │ next:null│
└──────────┘    └──────────┘    └──────────┘

second.next = first; will redirect the next reference of the "second" object to its preceding node:

 first
 head
 tail            second          temp
  ↓               ↓               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │ next:null│
│          │ ←——— next     │    │          │
└──────────┘    └──────────┘    └──────────┘

Note how this detaches the third object from the list. Luckily we still have a reference to it via temp, otherwise we would have for ever lost it. And of course, this was the very reason to introduce the temp variable.

The next two statements will prepare the loop for its next round: the first and second references are updated to refer to the next node. This way the loop will be able to go from head to tail through the list.

first = second; results in this state:

 head            first
 tail            second          temp
  ↓               ↓               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │ next:null│
│          │ ←——— next     │    │          │
└──────────┘    └──────────┘    └──────────┘

And after second = temp; we have:

 head                            second
 tail            first           temp
  ↓               ↓               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │ next:null│
│          │ ←——— next     │    │          │
└──────────┘    └──────────┘    └──────────┘

Second iteration:

const temp = second.next; initialises a new reference (the old temp only existed in the previous iteration). But as now second refers to the last node in the list, its next property is null, and so temp is null:

 head
 tail            first           second          temp: null
  ↓               ↓               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │ next:null│
│          │ ←——— next     │    │          │
└──────────┘    └──────────┘    └──────────┘

second.next = first; will redirect the next reference of the "second" object (which is the third object now) to its preceding node, as that is what first is referencing:

 head
 tail            first           second          temp: null
  ↓               ↓               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │          │
│          │ ←——— next     │ ←——— next     │
└──────────┘    └──────────┘    └──────────┘

The next two statements will prepare the loop for a potential next round: the first and second references are updated again to refer to the next node:

first = second; results in this state:

 head                            first
 tail                            second          temp: null
  ↓                               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │          │
│          │ ←——— next     │ ←——— next     │
└──────────┘    └──────────┘    └──────────┘

And after second = temp; we have:

 head                                            second: null
 tail                            first           temp: null
  ↓                               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next: ——————→ │          │    │          │
│          │ ←——— next     │ ←——— next     │
└──────────┘    └──────────┘    └──────────┘

Now the loop condition is false, so we exit the loop. At this moment we are sure that all next references are reversed, except the one in the first node, which should become null. And we also need to still adjust head so that it points to the last node. This is exactly what the remaining two assignments after the loop perform, and so we end up with:

                                 first           second: null
 tail                            head           (temp is out of scope)
  ↓                               ↓ 
┌──────────┐    ┌──────────┐    ┌──────────┐
│ value: 1 │    │ value: 2 │    │ value: 3 │
│ next:null│ ←——— next     │ ←——— next     │
└──────────┘    └──────────┘    └──────────┘

Now the list has reversed, and both head and tail reference the nodes that they should reference.

The algorithm

Concluding, this algorithm maintains three references that move along the list: first, second and temp. As long as they don't become null they always refer to 3 consecutive nodes in the list, and in each iteration they reference one node further down the list. This trio sticks together and walks from "left to right" in close collaboration.

Each node that get referenced by second will get its next reference updated so it refers to its preceding node. temp ensures that it is still possible to move along the remainder of the list, even though it is detached by this update of next.