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

  「题目：」

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

  「示例：」

  输入：head = [1,2,3,4,5], n = 2, 输出：[1,2,3,5].

  「解题思路：」

• 删除链表元素的核心操作是：preNode.next = preNode.next.next。

• 由于链表中的首元素也是可以被删除的，所以需要在首元素之前创建一个元素来处理这种场景。

• 由于链表只能从前往后遍历，所以要想删除倒数第 n 个结点，需要先遍历一次链表获取总长度，再求出该元素处于链表中的第几位。

  时间复杂度：O(n)，空间复杂度：O(1)。

const removeNthFromEnd = (head, n) => {
  const dummyHead = new ListNode(-1);
  dummyHead.next = head;
  let currentHead = dummyHead.next;
  let len = 0;
  while (currentHead) {
    len++;
    currentHead = currentHead.next;
  }

  currentHead = dummyHead;
  let index = len - n;
  while (index) {
    index--;
    currentHead = currentHead.next;
  }

  currentHead.next = currentHead.next.next;

  return dummyHead.next;
}

  针对上述计算删除元素的位置的思路，可以使用 双指针技巧 优化：

const removeNthFromEnd = (head, n) => {
  const dummyHead = new ListNode(null);
  dummyHead.next = head;

  let first = dummyHead;
  let second = dummyHead;
  for (let i = 0; i < n + 1; i++) {
    first = first.next;
  }

  while(first) {
    first = first.next;
    second = second.next;
  }

  second.next = second.next.next;
  return dummyHead.next;
}

82. 删除排序链表中的重复元素 II

  「题目：」

  给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。

  「示例：」

  输入：head = [1,2,3,3,4,4,5], 输出：[1,2,5].

  「解题思路：」

  由于链表本身就是有序的，所以只需要在遍历的过程中比较相邻元素即可去重，另外为了后续的删除操作，需要保存出现重复元素的前置节点。

  时间复杂度：O(n)，空间复杂度：O(1)。

const deleteDuplicates = head => {
  if (!head || !head.next) {
    return head;
  }
  const newHead = new ListNode(null);
  newHead.next = head;

  let preHead = newHead;
  let currentHead = head;
  while (currentHead && currentHead.next) {
    const currentValue = currentHead.val;
    let nextHead = currentHead.next;
    let isDuplicate = false;
    while (nextHead && currentValue === nextHead.val) {
      nextHead = nextHead.next;
      isDuplicate = true;
    }
    
    if (isDuplicate) {
      preHead.next = nextHead;
    } else {
      preHead = currentHead;
    }
    currentHead = nextHead;
  }

  return newHead.next;
}

1171. 从链表中删去总和值为零的连续节点

  「题目：」

  给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

  删除完毕后，请你返回最终结果链表的头节点。

  「示例：」

  输入：head = [1,2,-3,3,1], 输出：[3,1], 提示：答案 [1,2,1] 也是正确的。

  「解题思路：」

  利用 前缀和 技巧可以快速地识别当前序列的总和是否为零：

  如果当前序列的前缀和出现重复，那么这个区间内的序列即是总和为零的序列。

• 涉及到删除操作，需要通过 dummyHead 来处理头节点可能被删除的场景。

• 需要利用哈希表存储当前前缀和对应的节点，这样便于触发删除操作时，快速找到前置节点。

• 删除掉总和为零的序列的同时，需要清除掉这些节点对应的前缀和。

  时间复杂度：O(n)，空间复杂度：O(1)。

const removeZeroSumSublists = head => {

  const dummyHead = new ListNode(null);
  dummyHead.next = head;

  const sumRecord = new Map();
  let sum = 0;
  sumRecord.set(sum, dummyHead);

  while (head) {
    sum += head.val;
    if (sumRecord.has(sum)) {
      let removeHead = sumRecord.get(sum).next;
      let tempSum = sum;
      while (removeHead !== head) {
        tempSum += removeHead.val;
        sumRecord.delete(tempSum);
        removeHead = removeHead.next;
      }
      sumRecord.get(sum).next = head.next;
    } else {
      sumRecord.set(sum, head);
    }
    head = head.next;
  }

  return dummyHead.next;
}

2095. 删除链表的中间节点

  「题目：」

  给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

  长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

  「示例：」

  输入：head = [1,3,4,7,1,2,6], 输出：[1,3,4,1,2,6].

  「解题思路：」

  如果通过链表的总长度来计算中间节点，那么就需要：

• 第一次遍历链表获取其总长度并计算出中间节点的下标。

• 第二次遍历找到删除节点的前置节点。

  采用 快慢指针 可以巧妙的将两次遍历合成一次。

  时间复杂度：O(n)，空间复杂度：O(1)。

const deleteMiddle = function(head) {
    if (!head.next) {
        return null;
    }
    let fast = head;
    let slow = head;
    let pre = null;
    while (fast && fast.next) {
        fast = fast.next.next;
        pre = slow;
        slow = slow.next;
    }

    pre.next = slow.next;

    return head;
};

写在最后

  「感谢您能耐心地读到这里，如果本文对您有帮助，欢迎点赞、分享、或者关注下方的公众号哟。」

  相关链接：

• https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

• https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

• https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

• https://leetcode-cn.com/problems/delete-the-middle-node-of-a-linked-list/