题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
样例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
算法1
(快慢指针) $O(n)$
让快指针先走n步,慢指针再跟上,删除。
时间复杂度
最坏情况,两个指针都遍历整个链表,时间复杂度$O(n)$
参考文献
C++ 代码
/**
* 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 *dummy = new ListNode(0);
dummy->next = head;
ListNode *slow = dummy, *fast = head;
while (n-- && fast) fast = fast->next;
while (fast){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
slow = dummy->next;
delete dummy; dummy = nullptr;
return slow;
}
};
快慢指针就是双指针算法吗
算是其中一种吧 双指针有很多种 不用纠结名字其实 体会思想就行