删除链表的倒数第n个节点的最优算法实现

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

提示：

链表中结点的数目为 sz

• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

具体实现

要删除链表的倒数第 n 个节点，并返回链表的头节点，我们可以使用一趟扫描的方法来实现。这个方法涉及使用两个指针：快指针和慢指针。快指针先向前移动 n 步，然后慢指针从链表的头节点开始，与快指针同时移动。当快指针到达链表的末尾时，慢指针所在的下一个节点就是倒数第 n 个节点。

以下是使用 Java 实现的删除链表倒数第 n 个节点的函数：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); // 创建一个哑节点，它的下一个节点是头节点
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指针先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        // 快慢指针同时移动，直到快指针指向链表的末尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 慢指针的下一个节点就是倒数第 n 个节点，删除它
        slow.next = slow.next.next;

        return dummy.next; // 返回哑节点的下一个节点，即新的头节点
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

使用示例：

public class Main {
    public static void main(String[] args) {
        // 示例 1
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = new ListNode(4);
        head1.next.next.next.next = new ListNode(5);
        int n1 = 2;
        ListNode newHead1 = new Solution().removeNthFromEnd(head1, n1);
        printList(newHead1); // 应该输出 [1,2,3,5]

        // 示例 2
        ListNode head2 = new ListNode(1);
        int n2 = 1;
        ListNode newHead2 = new Solution().removeNthFromEnd(head2, n2);
        printList(newHead2); // 应该输出 []

        // 示例 3
        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(2);
        int n3 = 1;
        ListNode newHead3 = new Solution().removeNthFromEnd(head3, n3);
        printList(newHead3); // 应该输出 [1]
    }

    private static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

代码输出结果与题目中的示例输出是一致， V 哥的这个实现中，使用了一个哑节点来简化边界条件的处理，这样即使要删除的是头节点，代码也能正常工作。这个方法只需要一趟扫描，因此时间复杂度是 O(sz)，其中 sz 是链表的长度。

实现过程和步骤如下

下面 V 哥把实现过程再详细说明一下，为了帮助你更好的理解代码的逻辑实现：

1. 创建一个哑节点（dummy node），并将其设置为链表的头节点之前的一个节点。哑节点的引入是为了简化边界条件的处理，特别是当需要删除的节点是头节点时。

2. 初始化两个指针：快指针（fast）和慢指针（slow），它们都指向哑节点。

3. 快指针先向前移动 n 步。这样，快指针和慢指针之间就保持了 n 个节点的距离。

4. 快指针和慢指针同时向前移动，直到快指针到达链表的末尾（即快指针的下一个节点为 null）。此时，慢指针的位置就是倒数第 n 个节点的前一个节点。

5. 修改慢指针的 next 指针，使其指向下一个节点的下一个节点，从而跳过倒数第 n 个节点，实现删除操作。

6. 返回哑节点的下一个节点，即新的头节点。

这个方法的核心思想是利用快慢指针的差距来找到倒数第 n 个节点。快指针先走 n 步，然后快慢指针一起移动，直到快指针到达链表末尾。此时，慢指针所在的位置就是倒数第 n 个节点的前一个节点，这样就可以很容易地删除倒数第 n 个节点。

小结

V哥经过测试，坐实了这个方法只需要一趟扫描，所以时间复杂度是 O(sz)，其中 sz 是链表的长度。空间复杂度是 O(1)，因为只需要常数级别的额外空间来存储快慢指针和哑节点。