leetcode题解19：删除链表的倒数第N个结点

描述

该题来自于力扣第19题

给你一个链表，删除链表的倒数第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]

提示：

链表中结点的数目为sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

分析

想找到倒数第n个结点，就相当于找到第sz - n + 1个结点，但是sz不知道，需要一趟遍历整个链表才能获得，这样看来无论如何都需要两遍扫描；还记得找到中点结点的方法吗？快慢指针，一遍扫描即可；这里也可以用类似的想法；比如，现有一链表如下，要删除倒数第2个结点：

1 -> 2 -> 3 -> 4 -> 5 -> 6

如果我们能够让第一个指针p1指向4，那么就可以进行删除操作了；利用快慢指针的想法，第二个指针p2需要指向最后一个结点即6，所以两个指针相差2个结点，如果最开始让p1指向1，p2指向3，然后只需让p1++,p2++直到p2到达最后一个结点，这时p1自然达到了倒数第n个结点了。

所以先让p2指针往右走n步，达到第n+1个结点，然后p1,p2指针同时走动1步，直到p2指针指向sz，这时p1自然会指向sz -n，即要删除结点的父结点位置，然后就可以删除了。当然，还要考虑特殊情况：删除一个结点的时候的特殊处理。或者用一个虚假的头指向链表原有head，这样就不用考虑特殊情况了。

算法

采用双指针法，

初始化p1=head,p2=head
进入循环p2 = p2->next，直到i==n，如果p2==null，表明删除的是头结点，则让head = p1->next退出程序，或则进入3
进入循环p1 = p1->next, p2=p2->next，直到p2->next == null，表明p2已到达最后一个结点，此时让p1->next = p1->next->next

代码

python3

class Solution:
    def removeNthFromEnd(self, head, n):
        p1, p2 = head, head
        i = 0
        while i < n and p2 is not None:
            p2 = p2.next
            i += 1

        if p2 is None:
            head = p1.next
            return head

        while p2.next is not None:
            p1 = p1.next
            p2 = p2.next
        p1.next = p1.next.next

        return head

c++

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p1 = head;
        ListNode* p2 = head;
        int i = 0;
        while(i < n && p2 != nullptr){
            p2 = p2->next;
            i++;
        }
        if(p2 == nullptr){
            head = head->next;
            return head;
        }

        while(p2->next != nullptr){
            p1 = p1->next;
            p2 = p2->next;
        }
        p1->next = p1->next->next;
        return head;
    }
};

java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p1 = head;
        ListNode p2 = head;
        int i = 0;
        while(i < n && p2 != null){
            p2 = p2.next;
        }
        if(p2 == null){
            head = head.next;
            return head;
        }
        while(p2.next != null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p1.next = p1.next.next;
        return head;
    }
}