Lt19. 删除链表的倒数第 N 个节点、快慢指针

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

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

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

思路

反向链表

得到链表的反向链表值数组，再重新生成链表即可，其实上不符合题目删除的要求

两次遍历

一次遍历得到链表长度，第二次遍历的时候删除，使用一个哑结点处理删除首节点的问题，删除点的下标为length + 1 - n

快慢指针

使用一个哑结点处理删除首节点的问题，先令快指针走 n+1 步，再令快慢指针同时走，当快指针指向 null 时，说明到达链表尾部，将慢指针的 next 指向下下个节点即可

解答

反向链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  if (!head) return null;
  const list = [];
  while (head) {
    list.push(head.val);
    head = head.next;
  }
  let count = 0;
  let deleteIndex = list.length + 1 - n;
  let res = new ListNode();
  let temp = res;
  while (list.length) {
    const node = new ListNode(list.shift());
    if (++count !== deleteIndex) {
      temp.next = node;
      temp = temp.next;
    }
  }
  return res.next;
};

二次遍历

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  if (!head || !head.next) return null;
  let res = new ListNode();
  res.next = head;
  let temp = head;
  let length = 0;
  while (temp) {
    length++;
    temp = temp.next;
  }
  const deleteIndex = length + 1 - n;
  length = 0;
  temp = res;
  while (++length !== deleteIndex && temp) {
    temp = temp.next;
  }
  temp.next = temp.next.next;
  return res.next;
};

快慢指针

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  if (!head || !head.next) return null;
  let res = new ListNode();
  res.next = head;
  let slow = res;
  let fast = res;
  for (let i = 0; i < n + 1; i++) {
    fast = fast.next;
  }
  while (fast) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return res.next;
};