LeetCode | 19 删除链表的倒数第N个节点

题目

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

示例

给定一个链表：1->2>3->4->5，和 n=2。当删除倒数第二个节点后，链表变为 1->2>3->5。

说明

给定的 n 保证是有效的。

解题

这个题使用双指针即可很快解决：

1. 初始化两个指针 p1 和 p2 均指向链表的头部
2. p2 不动，p1 指针向后滑动 n 个位置
3. p1 和 p2 一起向后滑动，当 p1 指向节点的下一个节点为空时，p2 指向的节点即为待删除节点的前一个节点，执行删除操作。
4. 返回头指针

使用 C 语言实现如下：

LeetCodeSolution19.cview raw

// 链表节点定义
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

ListNode *delete(ListNode *head, int n) {
    if (head == NULL) return;
    ListNode *p1 = head, *p2 = head;
    // 滑动指针 p1
    for (; n > 0; n--)
        p1 = p1->next;
    // 同时滑动 p1 和 p2 直到 p1 指向最后一个节点
    while (p1->next != NULL) {
        p1 = p1->next;
        p2 = p2->next;
    }
    // 删除节点
    ListNode *tmp = p2->next;
    p2->next = tmp->next;
    if (tmp == head)
        head = tmp->next;
    free(tmp); // 释放
    return head;
}