LeetCode 19. 删除链表的倒数第 N 个节点 - 双指针解法详解 - 常规

LeetCode 19: 删除链表的倒数第 N 个节点 - 双指针解法详解

题目描述： 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

错误解法：

public ListNode removeNthFromEnd(ListNode head, int n) {
    if(head==null) {
        return head;
    }
    ListNode temp =head;
    int total=0;
    while(temp.next!=null) {
         total++;
         temp=temp.next;
    }
    int index =total-n;
    if(index==0) {
        return head.next;
    }
    ListNode pre=head;
    ListNode next =head.next;
    
    for(int i=0;i<index;i++) {
        pre=pre.next;
        next=next.next;
    }
    pre.next=next.next;
    return head;
}

这段代码的思路是先遍历整个链表，计算链表长度，然后再根据要删除的节点的位置进行删除操作。这样做的时间复杂度为 O(n)，而题目要求的时间复杂度为 O(1)。

正确思路：

使用双指针，首先让一个指针先走 n 步，然后让两个指针同时往后走，直到第一个指针走到链表末尾。此时第二个指针所指的节点就是要删除的节点的前一个节点，直接将其 next 指向下一个节点即可。需要注意的是，当要删除的节点是头节点时，需要特殊处理。

正确代码：

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    for(int i = 0; i <= n; i++) {
        first = first.next;
    }
    while(first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

代码解释：

创建一个虚拟头节点 dummy，并将 dummy.next 指向链表的头节点 head。这样做是为了方便处理删除头节点的情况。
使用 first 和 second 两个指针，分别指向 dummy 节点。
让 first 指针先走 n 步。
然后让 first 和 second 两个指针同时往后走，直到 first 指针走到链表末尾。
此时 second 指针所指的节点就是要删除的节点的前一个节点，将其 next 指向下一个节点即可。
返回 dummy.next，即为删除节点后的链表的头节点。

时间复杂度分析：

该算法的时间复杂度为 O(1)，因为我们只遍历了链表一次。

空间复杂度分析：

该算法的空间复杂度为 O(1)，因为我们只创建了常数个额外的节点。

总结：

使用双指针是解决 LeetCode 19 题的最佳方法，它可以将时间复杂度降至 O(1)。在实际应用中，如果需要频繁删除链表的倒数第 n 个节点，使用双指针方法可以显著提高效率。

其他相关知识点：

链表的基本操作，如创建链表、遍历链表、插入节点、删除节点等。
双指针技巧的应用场景，如链表的反转、链表的合并等。
时间复杂度和空间复杂度分析。

希望本文能够帮助您更好地理解 LeetCode 19 题，并掌握使用双指针解题的技巧。