【C/C++】删除链表的倒数第 N 个结点（leetcode T19）

考点预览：

双指针法：通过维护两个指针来一次遍历链表，避免了多次遍历链表的低效方法。
边界条件：要特别处理删除头结点的情况。

题目描述：

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

`详细解析：`

struct ListNode {
     int val;
     struct ListNode *next;
 };
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    struct ListNode *p1, *p2;
    p1 = head;
    p2 = head;
    int i;
    for (i = 0; i < n;i++)
    {
        p1 = p1->next;
    }
    if(p1==NULL)
    {
        return head->next;
    }
    while(p1->next!=NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    p2->next = p2->next->next;
    return head;
}

题目解析

给定一个链表，删除链表的倒数第 n 个节点，并返回链表的头结点。我们可以通过双指针的方法来高效解决这个问题，避免对链表进行多次遍历。

思路分析

初始化两个指针：我们使用两个指针 p1 和 p2，并将它们都指向链表的头部。
让 p1 先走 n 步：首先，我们让 p1 指针先走 n 步，这样 p1 和 p2 之间就有了 n 个节点的间隔。
同时移动两个指针：接着，我们同时移动 p1 和 p2，直到 p1 到达链表的末尾。此时，p2 就会指向倒数第 n 个节点的前一个节点。
删除节点：由于 p2 指向的是倒数第 n 个节点的前一个节点，我们可以通过 p2->next = p2->next->next 来删除目标节点。
特殊情况：如果 p1 在走 n 步后就已经为 NULL，说明要删除的是头结点。此时直接返回 head->next 即可。