Решение в JS. Отменить связанный список

Уровень — легкий

Учитывая следующий вопрос.

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Связный список состоит из узлов, объекта со значением и указателя. Бывают трех типов: одинарные, двойные и круговые.

Односвязный список только в одну сторону, не может идти назад. Он содержит 2 ключ-значение, значение (val) и следующий.

Двусвязный список является двусторонним, может идти вперед и назад. Он содержит 3 ключ-значение, значение (значение), следующее и предыдущее (предыдущее).

Обычно связанный список является линейным, причем голова является первым узлом, а хвост — последним узлом, причем последний указатель указывает на ноль.

Круговой связанный список не имеет конечного или хвостового узла. Так называемый последний/хвостовой узел указывает на N-й узел вместо нулевого.

Let create a new Node. Each node are not connected.
let one = new Node(1)
let two = new Node(2)
let three = new Node(3)
let four = new Node(4)
1  2  3  4 
The node are connect to another using the next property.
one.next = two
two.next = three
three.next = four
1->2->3->4->null
Version1 
Node {
  val: 1,
  next: Node { val: 2, next: Node { val: 3, next: Node { val: 4, next: null} } }
}

Version2
Node {
  val: 1,
  next: Node { 
           val: 2, 
           next: Node { 
                     val: 3, 
                     next: Node{ 
                               val: 4, 
                               next: null
                               }
                      }
              }
      }

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

H        T
1->2->3->4->null
      T        H
null<-1<-2<-3<-4
function reverse(head) {
   let previousNode = null
   while(head !== null){
      let nextNode = head.next
      head.next = previousNode
      previousNode = head
      head = nextNode
   }
   return previousNode
}

Сначала нам нужно создать предыдущий узел и установить для него значение null.
В настоящее время мы находимся в голове, узле 1.
Пока голова не нулевая, мы можем что-то с ней сделать.
Сначала нам нужно создать вызов временной переменной nextNode. Используя head.next, мы присваиваем nextNode = node 2.
Теперь нам нужно изменить направление указателя, вместо того, чтобы указатель указывал на узел 2, мы хотим, чтобы указатель указывал на предыдущий узел, который равен нулю.
После изменения направления .next мы можем обновить предыдущий узел и голову, чтобы перейти к следующей итерации. Назначьте previousNode = node 1 и head = node 2.
Помните, что порядок имеет значение, как вы называете свои переменные.

previousNode = head       previousNode = node 1
head = nextNode           head = node 2
head = nextNode           head = node 2
previousNode = head       previousNode = node 2

8. Наконец, верните предыдущийNode. Если указанный связанный список недействителен, он вернет null, иначе он вернет обратно связанный список.

Решение в JS. Отменить связанный список

Похожие вопросы