Question 399413 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – 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).

Tags:

2

Answers


  1. 0

    1–>2—>3—>4

    first = 1–>

    second = 2–>3–>

    In while
    1º)
    temp = 3–>4

    second.next = 1–>2–>

    first = 2–>1–>

    second = 3–>

    2º)
    temp = 4

    second.next=2–>1–>

    first = 3–>2–>1–>

    second = 4
    3º)
    temp = null

    second.next = 3–>2–>1–>

    first = 4–>3–>

    second = null

    4º)Out while

    next 1 = null

    head = 4–>3–>2–>1

    Login or Signup to reply.
  2. 0

    A linkedList is basically sequential nodes with pointers to the next one in the list. The while loop in there is essentially taking that pointer and pointing it to the previous one instead of the next one which is why we have to hold a reference to the "temp" node.

    The loop holds a reference to 3 sequential nodes at a time and it is "flipping" the pointer to second one only.

    // before the first loop:  
// it sets first to the head  
// it sets first to the tail  
// it sets second to the node that first is pointing to  

[first = node1] ---> [second = node2] --->   

// in the loop:  
// it only holds reference to what is inside the ( )  
([first = node1] ---> [second = node2] --->) [node3] ---> 

// add reference to the third node so we don't lose it 
const temp = second.next;  
([first = node1] ---> [second = node2] ---> [temp = node3] --->) [node4] --->  

// set the reference of the second node to the first instead of third  
second.next = first;  
([first = node1] **<--->** [second = node2] <-*no more pointer here*-> [temp = node3] --->) [node4] ---> 
 
// shift the nodes  
first = second; 
[first = node2] <---> [second = node2] <-*no more pointer here*-> [temp = node3] --->)   [node4] ---> 


// shift the nodes  
second = temp;    
[first = node2] <---> [second = node3] <-*no more pointer here*-> [temp = node3] --->)   [node4] ---> 

// Sooo, after the first loop:  
[node1] <--->( [first = node2]     [second = node3] ) ---> [node4] --->  

// We have changed the direction of the pointer of the second node to  
// point at the first node instead of the third. Because we have removed 
// that pointer, if we hadn't saved the third node in "temp" we would have 
// lost a reference to the rest of list.

// for the next loop:  
[node1] <---> ( [first = node2]     [second = node3] ) ---> [temp = node4] --->

// after sequential loops:  
[node(n)] <--- ([node(n+1)]   [node(n+2)]) ---> [node(n+3)] ---> 

// after the loop:  
[node1] <---> [node2] <--- [node3] <--- [node4]

// Finally, It sets the old heads pointer to null:  
this.head.next = null;  
[node1] **<---** [node2] <--- [node3] <--- [node4]

// Then sets the new head to the last node we have a reference to, which 
// is first (previously the tail)  
this.head = first;
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search