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

题目

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

进阶：你能尝试使用一趟扫描实现吗？

题解

计算链表长度

1. 遍历一次计算出链表长度 l
2. 要删除的节点就是 l-n-1

/**
 * 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) {
  // 遍历计算链表长度
  let l = 0;
  let node = head;
  while (node) {
    node = node.next;
    l++;
  }

  // 删除头节点
  if (n == l) return head.next;

  // 找到要删除的节点
  let index = 0;
  node = head;
  while (index < l - n - 1) {
    node = node.next;
    index++;
  }
  node.next = node.next.next;
  return head;
};

时间复杂度：O(l) 空间复杂度：O(1)

栈

利用栈的特性，先将所有节点入栈，然后出栈第 n 个节点就是需要删除的

/**
 * 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) {
  let s = [];
  let node = head;

  // 入栈
  while (node) {
    s.push(node);
    node = node.next;
  }

  if (s.length == n) return head.next;

  // 出栈
  let c = 0;
  // 要删除的前一个节点
  let delPreNode = null;
  while (s.length && c <= n) {
    delPreNode = s.pop();
    c++;
  }
  delPreNode.next = delPreNode.next.next;
  return head;
};

时间复杂度：O(l) 空间复杂度：O(l)

双指针

/**
 * 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) {
  // 添加虚拟头节点，统一删除头节点的情况
  let xhead = new ListNode(0, head);
  let p1 = xhead.next;
  let p2 = xhead;
  let c = 0;

  while (c < n) {
    p1 = p1.next;
    c++;
  }
  while (p1) {
    p1 = p1.next;
    p2 = p2.next;
  }
  p2.next = p2.next.next;
  return xhead.next;
};