跳到主要内容

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

题目描述​

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

出处：LeetCode

解法一：栈​

思路​

我们也可以使用栈来删除链表的倒数第 n 个结点。我们首先遍历链表，将链表的所有节点依次入栈。然后我们再次遍历链表，每次遍历时，我们将栈顶的节点出栈，直到出栈 n 次。此时，栈顶的节点就是链表的倒数第 n 个节点的前一个节点。我们将栈顶的节点的下一个节点指向下下个节点，即可删除倒数第 n 个节点。

实现​

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;

  const stack: ListNode[] = [];
  let cur: ListNode | null = dummy;

  while (cur !== null) {
    stack.push(cur);
    cur = cur.next;
  }

  for (let i = 0; i < n; i++) {
    stack.pop();
  }

  const prev = stack[stack.length - 1];
  prev.next = prev.next!.next;

  return dummy.next;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是链表的长度
  • 空间复杂度：O(n)O(n)

解法二：双指针​

思路​

我们可以使用双指针来删除链表的倒数第 n 个结点。我们定义两个指针 slow 和 fast，分别指向链表的头结点 head。然后我们先让 fast 指针向后移动 n 个节点。接着，我们让 slow 指针和 fast 指针同时向后移动，直到 fast 指针指向链表的尾节点。此时，slow 指针指向的节点就是链表的倒数第 n 个节点的前一个节点。我们将 slow 指针的下一个节点指向下下个节点，即可删除倒数第 n 个节点。

实现​

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0);
  dummy.next = head;

  let slow: ListNode | null = dummy;
  let fast: ListNode | null = dummy;

  for (let i = 0; i < n; i++) {
    fast = fast!.next;
  }

  while (fast!.next !== null) {
    slow = slow!.next;
    fast = fast!.next;
  }

  slow!.next = slow!.next!.next;

  return dummy.next;
}

复杂度分析​

  • 时间复杂度：O(n)O(n)，其中 nn 是链表的长度。
  • 空间复杂度：O(1)O(1)