博客

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

难度 中等

给定一个链表，删除链表的倒数第

n

个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的

n

保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

双指针

使用两个指针遍历链表，其中前指针和后指针间隔为 n 。当前指针遍历到 nullptr 时，后指针正好指向需要删除的结点

（需要注意 n 等于链表长度时头结点被删除的特例）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //前后指针和当前结点指针(用于删除结点)
        ListNode *post = head, *pre = head, *current;
        //使前后指针间隔n
        for (int i = 1; i <= n; i++) {
            pre = pre->next;
        }
        //间隔后若前指针已经指向nullptr，说明删除的是头结点，直接返回头结点的后继
        if (pre == nullptr) return head->next;
        //前后指针遍历链表，并删除指定结点
        while (pre != nullptr) {
            current = post;
            post = post->next;
            pre = pre->next;
        }
        current->next = post->next;
        return head;
    }
};