删除链表的倒数第 N 个结点

题目：

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

示例 1：

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

思路：

双指针思路： p1：先移动 n 步，与慢指针拉开 n 个节点的距离。p2：随后与 p1 同步移动，直到 p1 到达链表末尾。此时 p2 指向倒数第 n+1 个节点，直接修改其 next 指针即可删除目标节点。

代码：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)\
{
    //判断head 和 n是否正常
    if( NULL == head || n <= 0)
    {
        return NULL;
    }
    struct ListNode* p1 = head;
    struct ListNode* p2 = head;
    //防止 n 超过链表长度
    for(int i = 0; i < n; i++)
    {
        if(NULL == p1)
        {
            return head;//超过当前链表的长度
        }
        p1 = p1->next;
    } 
    //处理删除头节点的特殊情况,如果 p1 移动 n 步后正好变成 NULL，说明要删除的是头节点（即 n == 链表长度）。
    if(NULL == p1)
    {
        struct ListNode* pnew = head->next;
        free(head);
        return pnew;
    }
    // 同步移动 p1 和 p2
    while(p1->next != NULL)
    {
        p1 = p1->next;
        p2 = p2->next;
    }
    //删除p2->next
    struct ListNode* tmp =p2->next;
    p2->next = p2->next->next;
    free(tmp);
    return head;
}

代码分析：

输入验证

if (head == NULL || n <= 0)
{
    return head;
}

功能：

• 检查链表是否为空

• 验证n是否为有效正整数
  必要性：
  防止后续操作出现空指针异常或逻辑错误

双指针初始化

struct ListNode* p1 = head;
struct ListNode* p2 = head;

作用：

• 创建快(p1)、慢(p2)两个指针

• 初始都指向链表头部

快指针先行

for (int i = 0; i < n; i++) 
{
    if (p1 == NULL) 
    {   
        return head;
    }
    p1 = p1->next;
}

执行过程：

1. 快指针p1向前移动n步

2. 实时检测是否超出链表长度
   关键点：

• 建立n个节点的间距：当p1移动完成后，p2与p1间距保持为n

• 边界保护：避免n>链表长度时的越界访问

头节点删除处理

if (p1 == NULL)
{
    struct ListNode* pnew = head->next;
    free(head);
    return pnew;
}

触发条件：
p1移动n步后为NULL（说明n=链表长度）
操作逻辑：

1. 保存新头节点(head->next)

2. 释放原头节点内存

3. 返回新的链表头

同步移动阶段

while (p1->next != NULL) 
{
    p1 = p1->next;
    p2 = p2->next;
}

工作原理：

• 同步移动双指针直到p1到达末节点

• 此时p2停在倒数第n+1个节点

节点删除操作

struct ListNode* tmp = p2->next;
p2->next = p2->next->next;
free(tmp);

执行步骤：

1. 临时保存待删除节点(p2->next)

2. 修改指针跳过目标节点

3. 释放目标节点内存
   内存安全：

• 必须保存节点指针后再free

• 防止内存泄漏

结果返回

return head;

返回逻辑：

• 非头节点删除时返回原head

• 头节点删除时已在模块4返回newHead