JavaScript 删除链表的倒数第N个节点

题目描述 输入一个链表，输出该链表中倒数第k个结点。

思路

两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点；
然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。
本题考察鲁棒性，因此要判断空值和负值以及k值不能超过链表的长度。

function Node(element){
  this.element = element  //当前节点的元素
  this.next = null  //下一个节点链接
}
function List(){
  this.head = new Node("head")  //头节点
  this.find = find  //查找节点
  this.insert = insert  //插入节点
  this.remove = remove  //删除节点
  this.display = display  //显示链表
  this.findPrevious = findPrevious  //查找前一个节点 
}
//下面的函数是操作方法：对应List类构造函数中的名称
//查找给定节点
function find(item){
  var currNode = this.head
  console.log(currNode)
  while(currNode.element !== item){
    currNode = currNode.next
  }
  return currNode
}
//向链表插入一个节点
function insert(newElement, item){
  var newNode = new Node(newElement)
  var current = this.find(item)
  if(current == null){
    return console.log("can't find the item")
  }
  newNode.next = current.next
  current.next = newNode
}
//从链表中删除节点时，我们先要找个待删除节点的前一个节点，找到后，我们修改它的 next 属性，使其不在指向待删除的节点，而是待删除节点的下一个节点。那么，我们就得需要定义一个 findPrevious 方法遍历链表，检查每一个节点的下一个节点是否存储待删除的数据。如果找到，返回该节点，这样就可以修改它的 next 属性了。 
//查找待删除节点的前一个节点
function findPrevious(item){
  var currNode = this.head
  while(currNode.next != null && currNode.next.element != item){
    currNode = currNode.next
  }
  return currNode
}
//从链表中删除节点
function remove(item){
  var prevNode = this.findPrevious(item)
  if(prevNode.next != null){
    prevNode.next = prevNode.next.next
  }
}
//显示链表元素
function display(){
  var current = this.head
  while(current.next != null){
    console.log(current.next.element)
    current = current.next
  }
}

var removeKthToTail = function(head, k){
  if (head.element === undefined){
    return new Error("head为空链表！")
  }
  if(k <= 0){
    return new Error("k小于等于0！")
  }
  let pre = head
  let last = head
  for(var i = 1; i < k; i++){
    if(pre.next !== null){
      pre = pre.next
    } else {
      return new Error("k值过大！")
    }
  }
  while(pre.next !== null){
    pre = pre.next
    last = last.next
  }
  return last
}

let list = new List()
list.insert("Kobe",'head')
list.insert("Curry","Kobe")
list.insert("Russel","Curry")
list.insert("Klay","Russel")
list.insert("Tracy","Klay")
console.log(list.display())
console.log(removeKthToTail(list.head,2))

shinena / myProject

JavaScript 删除链表的倒数第N个节点 #40