方法:递归
/*** 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:int delN;int curN;bool isDelete=false;void recurveList(ListNode* a,ListNode* b){if(b==nullptr){return ;}recurveList(b,b->next);curN+=1;if(curN==delN){ListNode* c=b;a->next=c->next;delete b;isDelete=true;}}ListNode* removeNthFromEnd(ListNode* head, int n) {delN=n;curN=0;if(!head->next){delete head;return nullptr;}ListNode* res=head;recurveList(head,head->next);if(!isDelete){ListNode* temp=head;res=head->next;delete temp;}return res;}
};
方法:二次遍历
/*** 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) {int sumLength=0;ListNode* temp=head;while(temp){sumLength+=1;temp=temp->next;}temp=head;int leftLength=sumLength-n;if(leftLength==0){ListNode* deleteNode=head;head=head->next;delete deleteNode;return head;}int i=1;temp=head;while(i<leftLength){temp=temp->next;i+=1;}ListNode* deleteNode=temp->next;temp->next=temp->next->next;delete deleteNode;return head;}
};
方法:双指针+对称
/*** 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* fast=new ListNode(0,head);ListNode* slow=fast;ListNode* res=fast;while(n>0){n--;fast=fast->next;}while(fast->next){fast=fast->next;slow=slow->next;}ListNode* temp=slow->next;slow->next=slow->next->next;delete temp;temp=res;res=res->next;delete temp;return res;}
};