第一次提交:
/**
* 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) {
//虚拟头结点,防止出现空指针的情况比如说链表总共有 5 个节点,题目就让你删除倒数第 5 个节点,也就是第一个节点,那按照算法逻辑,应该首先找到倒数第 6 个节点。
但第一个节点前面已经没有节点了,这就会出错。
但有了我们虚拟节点 dummy 的存在,就避免了这个问题,能够对这种情况进行正确的删除。
ListNode* dummy=new ListNode(-1);
ListNode* p1=dummy;
ListNode* p2=dummy;
dummy->next=head;
// 删除倒数第 n 个,要先找倒数第 n + 1 个节点
for(int i=0;inext;
}
while(p1!=NULL){
p2=p2->next;
p1=p1->next;
}
p2->next=p2->next->next;
return dummy->next;
}
};
第二次提交:
/**
* 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(-1);
ListNode* p1;
ListNode* p2;
dummy->next=head;
p1=dummy;
p2=dummy;
for(int i=0;inext;
}
while(p1!=NULL){
p1=p1->next;
p2=p2->next;
}
//此时p2已经指向了倒数第N+1个结点
p2->next=p2->next->next;
return dummy->next; //注意这里一定要是return dummy->next!!!不能return head!!!
}
};
思路:
1.要删除倒数第n个节点,就要找到倒数第n+1个节点,让这个节点的next等于它的next的next。
2.在找倒数第n+1个节点的时候,先让p1提前走n+1布,再让p2出发。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)