Перевернуть связанный список ... что не так с моей реализацией? - PullRequest
Новая
       15

Перевернуть связанный список ... что не так с моей реализацией?

1 голос
/ 11 апреля 2020

У меня проблемы с обращением связанного списка на основе моей реализации ниже. Что-то не так или отсутствует, что я здесь делаю? 

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

class SinglyLinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }

    push(val) {
        var newNode = new Node(val);

        var current = this.head; 

        if (!this.head) 
            this.head = newNode; 
        else {

            // iterate to the end of the 
            // list 
            while (current.next) { 
                current = current.next; 
            } 

            // add node 
            current.next = newNode; 
        } 
        this.length++;

        return this; 
    }

    // reverse the list
    reverse() {
        var prev = null;
        var curr = this.head;
        while (curr !== null) {
            var temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }

        return this;
    }

    print() {
        var arr = []
        var current = this.head;

        while(current) {
            arr.push(current.val);
            current = current.next; 
        }

        console.log(arr);
    }
}

Вот моя реализация, когда я создаю объект и пу sh некоторые узлы 

var list = new SinglyLinkedList();
list.push(1);
list.push(2);
list.push(3);
list.push(4);

Каждый раз, когда я запускаю list.reverse() затем list.print() печатает только [1], а не [4,3,2,1].

Ответы [ 2 ]

3 голосов
/ 11 апреля 2020

Вы правильно переворачиваете ссылки между узлами, но никогда не меняете то, на что указывает this.head, поэтому теперь оно указывает на конец списка, а не на начало списка. Поэтому, когда вы вызываете print, print начинается с последнего узла и затем некуда go. 

  reverse() {
      var prev = null;
      var curr = this.head;
      while (curr !== null) {
          var temp = curr.next;
          curr.next = prev;
          prev = curr;
          curr = temp;
      }
      this.head = prev; // <--- added
      return this;
  }
0 голосов
/ 11 апреля 2020

Вы не обновили свойство head в вашем методе reverse. Просто добавьте this.head = prev; после while l oop, и я считаю, что оно должно работать.

...