从单链表中删除节点

Question

我在Javascript中为LL实现了一个删除函数。

下面是我的函数：

​

//Define Node obj
function Node(data){
  this.data = data;
  this.next = null;
}

//Define SinglyList obj
function SinglyList(){
  this._length = 0;
  this.head = null;
}

SinglyList.prototype.add = function(val){
  var node = new Node(val),
      currentNode = this.head;

      //If empty, build as first node
      if(!currentNode){
        this.head = node;
        this._length++;
        return;
      }

      //iterate over until end of list
      while(currentNode.next){
        currentNode = currentNode.next;
      }

      //add/append new node
      currentNode.next = node;
      this._length++;

      return node;
};

SinglyList.prototype.remove = function(index){
  var currentNode = this.head, count=0, previous;
  //if list is empty, exit out
  if(this._length===0) return;

  //Check if first node
  if(index===0){
      this.head = currentNode.next;
      this._length--;
  }else{

      while(count<index){
        previous = currentNode;
        currentNode = currentNode.next;
        count++;
      }//end while

      previous.next = currentNode.next;

      return previous;
  }// end if

};

var singlyList = new SinglyList();

singlyList.add(1);
singlyList.add(2);
singlyList.add(3);
singlyList.add(4);
singlyList.add(5);
singlyList.add(6);
singlyList.add(7);
singlyList.add(8);
singlyList.add(9);
singlyList.add(10);

console.log(JSON.stringify(singlyList));
console.log('Remove:\n'+JSON.stringify(singlyList.remove(5)));

​

问题:如果我的列表中有10个节点，并调用此函数来删除第5个节点，则此函数仅返回第4-10个节点，其中第5个节点被删除。然而，我预计它会返回1-10，其中5被删除。我做错了什么?如何检索只删除了第5个节点的列表？

Answer 1

尽管如此，你还是在代码中犯了一个小错误

1) while循环应该运行到< index-1，因为您从0开始计数

2)您没有执行此操作。_length--删除第一个节点以外的其他节点之后

3) JSON.stringify使用head元素开始打印，删除节点时返回的是前一个节点，因此得到的节点列表是错误的

更正后的代码在这里

//Define Node obj
function Node(data){
  this.data = data;
  this.next = null;
}

//Define SinglyList obj
function SinglyList(){
  this._length = 0;
  this.head = null;
}

SinglyList.prototype.add = function(val){
  var node = new Node(val),
      currentNode = this.head;

      //If empty, build as first node
      if(!currentNode){
        this.head = node;
        this._length++;
        return;
      }

      //iterate over until end of list
      while(currentNode.next){
        currentNode = currentNode.next;
      }

      //add/append new node
      currentNode.next = node;
      this._length++;

      return node;
};

SinglyList.prototype.remove = function(index){
  var currentNode = this.head, count=0, previous;
  //if empty, exit out
  if(this._length===0) return;

  //Check against first node
  if(index===0){
      this.head = currentNode.next;
      this._length--;
  }else{

      while(count<index-1){
        previous = currentNode;
        currentNode = currentNode.next;
        count++;
      }//end while

      previous.next = currentNode.next;
      this._length--;

      return this.head;
  }// end if

};

var singlyList = new SinglyList();

singlyList.add(1);
singlyList.add(2);
singlyList.add(3);
singlyList.add(4);
singlyList.add(5);
singlyList.add(6);
singlyList.add(7);
singlyList.add(8);
singlyList.add(9);
singlyList.add(10);

document.write(JSON.stringify(singlyList));
singlyList.remove(5)
document.write('After removing 5 :\n'+JSON.stringify(singlyList));