题目描述
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
样例
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
Note:当头结点有可能被删除掉时,我们可以定一个虚拟头结点,删除倒数第k个头节点,需要找到倒数k+1个节点
算法1
(枚举) $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 k) {
int n = 0;
auto dummy = new ListNode(-1);
dummy->next = head;
for(auto p = dummy ; p ; p = p ->next)n++;
auto p = dummy;
for(int i = 0; i < n - k - 1; i ++)p = p ->next; //n-(k+1)=> n - k - 1
p->next = p->next->next;
return dummy->next;
}
};
算法2
(双指针) $O(n)$
定义first和second两个指针,然后先让一个指针跑到距离第二个指针为n的位置,
然后再同时移动两个指针,直到一个指针走到终点,此时second就是倒数n + 1个节点
然后直接删除即可
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) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto first = dummy;
auto second = dummy;
for(int i = 0 ; i <= n ; i ++)first = first->next; //算上虚拟的头结点,所以是n + 1
while(first){
first = first->next;
second = second->next;
}
second->next = second->next->next;
return dummy->next;
}
};