给你一个链表,删除链表的倒数第 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]
/**
* 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) {
if(!head){return nullptr;}
ListNode* HEAD=new ListNode(0);//创建新节点
HEAD->next=head;//多创建一个节点,这样删除节点不用考虑是否是头节点
int cnt=0;
ListNode* pre=HEAD;
ListNode* cur=head;
while(cur){
cnt++;cur=cur->next;
}
//删除第cnt-n+1个节点,从第一个节点移动cnt-n次
cur=head;
for(int i=0;i<cnt-n;i++){
pre=pre->next;
cur=cur->next;
//printf("pre=%d,cur=%d\n",pre->val,cur->val);
}
pre->next=cur->next;
return HEAD->next;
}
};