Я не понимаю, как работает эта функция, которая является функциейverse() в реализации связанного списка

1-->2--->3--->4

первый = 1 -->

второй = 2-->3-->

В то время как 1°) температура = 3 -> 4

второй.следующий = 1 --> 2 -->

первый = 2 --> 1 -->

второй = 3 -->

2°) температура = 4

второй.следующий=2-->1-->

первый = 3-->2-->1-->

второй = 4 3°) температура = ноль

второй.следующий = 3-->2-->1-->

первый = 4-->3-->

второй = ноль

4º) Пока

следующий 1 = ноль

голова = 4-->3-->2-->1

LinkedList — это, по сути, последовательные узлы с указателями на следующий узел в списке. Цикл while по сути берет этот указатель и указывает его на предыдущий, а не на следующий, поэтому мы должны хранить ссылку на узел «temp».

Цикл хранит ссылку на 3 последовательных узла одновременно и «переворачивает» указатель только на второй.

// 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;

Как перевернуть связанный список в JavaScript

Я объясню код шаг за шагом.

Класс узла

Сначала мы определяем класс Node для представления каждого элемента связанного списка:

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

Класс LinkedList

Далее мы создаем класс LinkedList для управления узлами:

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(), который меняет связанный список на место:

  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.info(`Initial list: ${list}
      first = head = ${first.value}
      tail = head = ${this.tail.value}
      second = first.next = ${second.value}
    `);

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

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

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

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

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

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

      n++;
      console.info();
    }

    // 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();
  }
}

Пример использования

Чтобы увидеть метод reverse() в действии, вы можете создать связанный список и вызвать метод:

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

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

Объяснение

1. Инициализация:

   • first начинается в начале списка.
   • this.tail установлен на оригинальную голову.
   • second — это узел рядом с first.

2. Цикл по списку:

   • Сохраните следующий узел second в temp.
   • Переверните указатель second, чтобы он указывал на first.
   • Переместите first и second на шаг вперед.

3. Конец цикла:

   • Последний обработанный узел (first) становится новой головой.
   • Оригинальная голова (теперь this.tail) указывает на null.

4. Результат:

   • Связанный список перевернут, и вы можете распечатать перевернутый список для проверки.