I don't understand how this function works, which is reverse() function in implementation of a linked list

Here is code for implementing a singly-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;
  }

  prepend(value) {
    const newNode = {
      value: value,
      next: null,
    };
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }

  reverse() {
    if (!this.head.next) {
      return this.head;
    }
    let first = this.head;
    this.tail = this.head;
    let second = first.next;

    while (second) {
      const temp = second.next; //third
      second.next = first;
      first = second;
      second = temp;
    }

    this.head.next = null;
    this.head = first;
    return this.printList();
  }

}

I need someone to help me understand this reverse() function, I tried to understand it a lot of times, and I also tried with ChatGPT haha.

The reverse() function runtime is O(n).

How to Reverse a Linked List in JavaScript

I’ll explain the code step-by-step.

Node Class

First, we define the Node class to represent each element in the linked list:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

LinkedList Class

Next, we create the LinkedList class to manage the nodes:

class LinkedList {
  constructor(value) {
    const newNode = new Node(value);
    this.head = newNode;
    this.tail = this.head;
    this.length = 1;
  }

  append(value) {
    const newNode = new Node(value);
    this.tail.next = newNode;
    this.tail = newNode;
    this.length++;
    return this;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
    this.length++;
    return this;
  }

  insert(index, value) {
    if (index >= this.length) return this.append(value);
    if (index === 0 || this.length === 0) return this.prepend(value);
    const newNode = new Node(value);
    const leader = this.traverseToIndex(index - 1);
    const holdingPointer = leader.next;
    leader.next = newNode;
    newNode.next = holdingPointer;
  }

  traverseToIndex(index) {
    let counter = 0;
    let currentNode = this.head;
    while (counter !== index) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode;
  }

  printList() {
    let array = [];
    let currentNode = this.head;
    while (currentNode !== null) {
      array.push(currentNode.value);
      currentNode = currentNode.next;
    }
    return array;
  }

reverse() Method

Here is the reverse() method which reverses the linked list in place:

  reverse() {
    if (!this.head.next) {
      return this.head;
    }

    let first = this.head; // Start with the head node
    this.tail = this.head; // The tail will become the original head
    let second = first.next; // The second node

    // Print the initial state
    let list = this.printList();
    console.log(`Initial list: ${list}
      first = head = ${first.value}
      tail = head = ${this.tail.value}
      second = first.next = ${second.value}
    `);

    let n = 1;
    console.log(`While second is not null:`);

    // Reverse the pointers
    while (second) {
      console.log(`LOOP: ${n}
        ${list}
      `);

      const temp = second.next; // Store the next node
      if (temp !== null) console.log(`temp = second.next = ${temp.value}`);

      second.next = first; // Reverse the pointer of the current node
      console.log(`second.next = first = ${second.next.value}`);

      first = second; // Move first to the current node
      console.log(`first = second = ${first.value}`);

      second = temp; // Move second to the next node
      if (second !== null) console.log(`second = temp = ${second.value}`);

      n++;
      console.log();
    }

    // Final adjustments
    this.head.next = null; // The new tail should point to null
    this.head = first; // The new head is the last node we processed
    return this.printList();
  }
}

Usage Example

To see the reverse() method in action, you can create a linked list and call the method:

let myLinkedList = new LinkedList(10);
myLinkedList.append(5);
myLinkedList.append(16);

console.log(myLinkedList.reverse()); // Output: [16, 5, 10]

Explanation

1. Initialization:

   • first starts at the head of the list.
   • this.tail is set to the original head.
   • second is the node next to first.

2. Loop Through the List:

   • Store the next node of second in temp.
   • Reverse the pointer of second to point to first.
   • Move first and second one step forward.

3. End of Loop:

   • The last node processed (first) becomes the new head.
   • The original head (now this.tail) points to null.

4. Result:

   • The linked list is reversed, and you can print the reversed list to verify.