题目描述

题目链接

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

思路

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的指针指向了链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

例如，在本题中，如果我们要删除节点，我们需要知道节点的前驱节点，并将的指针指向的后继节点。但由于头节点不存在前驱节点，因此我们需要在删除头节点时进行特殊判断。但如果我们添加了哑节点，那么头节点的前驱节点就是哑节点本身，此时我们就只需要考虑通用的情况即可。

1. 计算链表长度

比较容易想到的方法是，我们首先从头节点开始对链表进行一次遍历，得到链表的长度。随后我们再从头节点开始对链表进行一次遍历，当遍历到第个节点时，它就是我们需要删除的节点。

如下示例：为了与题目中的保持一致，头节点的编号从开始。我们从哑节点开始遍历节点，当遍历到第个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

代码实现：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    // 计算链表长度
    int L = getLength(head);
    // 遍历至待删除节点的前驱节点
    ListNode cur = dummy;
    for (int i = 1; i < L - n + 1; ++i) {
        cur = cur.next;
    }
    // 删除节点
    cur.next = cur.next.next;
    return dummy.next;
}
private int getLength(ListNode head) {
    int L = 0;
    while (head != null) {
        ++L;
        head = head.next;
    }
    return L;
}

• 时间复杂度：，其中是链表的长度。

• 空间复杂度：。

  2. 栈

  我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第个节点就是需要删除的节点，并且栈顶的节点就是待删除节点的前驱节点。这样，我们就可以直接删除了。

  public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    Stack<ListNode> stack = new Stack<>();
    // 入栈全部节点
    ListNode cur = dummy;
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    // 出栈n个节点
    for (int i = 0; i < n; ++i) {
        stack.pop();
    }
    ListNode prev = stack.peek();
    prev.next = prev.next.next;
    return dummy.next;
  }
  

• 时间复杂度：，其中是链表的长度。

• 空间复杂度：，其中是链表的长度。主要为栈的开销

  3. 双指针

  我们也可以在不预处理出链表的长度，以及使用常数空间的前提下解决本题。

由于我们需要找到倒数第个节点，因此我们可以使用两个指针和同时对链表进行遍历，并且比超前个节点。当遍历到链表的末尾时，就恰好处于倒数第个节点。

具体地，初始时和均指向头节点。我们首先用对链表遍历次，此时和之间间隔了个节点，即比超前了个节点。之后，我们同时用和对链表进行遍历。当遍历到链表末尾时，恰好指向倒数第个节点。

根据方法一和方法二，如果我们能够得到的是倒数第个节点的前驱节点而不是倒数第个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将指向哑节点，其余的操作步骤不变。这样一来，当遍历到链表的末尾时，的下一个节点就是我们需要删除的节点。

代码实现：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode first = head;
    ListNode second = dummy;
    // 定位到第n个节点
    for (int i = 0; i < n; ++i) {
        first = first.next;
    }
    // 头节点和第n个节点同时向后走，当第n个节点走到链尾时，头节点即为倒数第n个节点
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    // 删除倒数第n个节点
    second.next = second.next.next;
    return dummy.next;
}

• 时间复杂度：，其中是链表的长度。
• 空间复杂度：。