每天一道leetcode(Day 34)

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

题目描述

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

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

解题思路

解法：快慢指针,需要删除链表中的倒数第 n 个节点，我们需要知道的就是倒数第 n+1 个节点，然后删除删除倒数第 n+1 节点的后继节点即可

步骤：

• 使用 2 个指针：fast 快指针提前走 n+1 步,slow 指针指向当前距离 fast 倒数第 n 个节点， 初始为 head

• 然后， fast 、 slow 同步向前走，直到 fast.next 为 null,此时，fast 为最后一个节点，slow 就是倒数第 n+1 个节点，此时问题就变更为删除链表中的 slow 的后继节点

• 但存在一个问题，当链表长度为 n 时，fast 是前进不到 n+1 个节点位置的，所以为了解决这个问题就需要创建一个头节点 preHead ，设置 preHead.next = head ，这样就可以解决以上问题，删除倒数第 n 个节点后，返回的 preHead.next 即可(当然也可以不创建 preHead 节点，在快指针走 n 步之后先判断 fast.next 是否为 null ，即 fast 是否是最后一个节点，如果是则删除 F 头节点)

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let preHead = new ListNode(0);
  preHead.next = head;
  let fast = preHead,
    slow = preHead;
  // 快先走 n+1 步
  while (n--) {
    fast = fast.next;
  }
  // fast、slow 一起前进
  while (fast && fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return preHead.next;
};

参考

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