Chaoszhu'Blog

Appearance

删除链表的倒数第N个结点 ​

LeetCode-19

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

js
// 思路：快指针先行n步，此时慢指针距离快指针n步。平行往后移动到结束节点就能得到start后面的节点就是要删除的节点
var removeNthFromEnd = function(head, n) {
  // 头虚拟节点(next指向头)
  let dummyHead = new ListNode(0)
  dummyHead.next = head

  let start = dummyHead // start指针
      end = dummyHead // end指针
  // end指针先行 n步
  while(n) {
    end = end.next
    n--
  }
  // 同步推进，直至end为最后一个节点
  while(end.next) {
    start = start.next
    end = end.next
  }
  // start指针的下一个节点即为需要删除的节点
  start.next = start.next.next

  return dummyHead.next // 返回头节点(head可能会被删除)
}