LeetCode热题100 删除链表的倒数第N个结点

题目描述

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

思路

1 我们可以使用两个指针，这两个指针之间的差距为n。
2 当快指针下一个节点是nullptr时，慢指针的下一个节点就是要删除的对象。
3 特殊情况：快指针先走了n步后，已经到达nullptr了，说明要删除的对象是头节点。

代码

/**
* 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) {
// 1 快慢指针相差n个单位
ListNode *fast = head;
ListNode *slow = head;
for(int i = 0; i < n; ++i)
{
fast = fast->next;
}
// 2 特殊判断删除头节点
if(fast == nullptr)
{
head = head->next;
delete slow;
}
// 3 删除中间节点
else
{
while(fast->next != nullptr)
{
fast = fast->next;
slow = slow->next;
}
ListNode *temp = slow->next;
slow->next = slow->next->next;
delete temp;
}
return head;
}
};