【LeetCode】LeetCode刷题(18)【中等】删除链表的倒数第 N 个结点(C++)
@[TOC](删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
题目——[链接](19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode) (leetcode-cn.com))
遍历统计方法
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head)//空的直接返回
{
return NULL;
}
int count = 0;//统计个数
ListNode* tempnode = head;
ListNode* temp = NULL;
int prev = 0;
while(tempnode)
{
count++;
tempnode = tempnode->next;
}
tempnode = head;
//一共就一个,也一并算到删除第一个结点
if(count == n)
{
temp = head;
head = head->next;
delete temp;
return head;
}
//删除第一个结点之后的结点
//循环拿到要删除结点的前一个结点
while(prev != count -n)
{
prev++;
//此时已经到了要删除结点的前一个结点,break
if(prev == count-n)
{
break;
}
tempnode = tempnode->next;
}
//只有一个元素 or 删除第一个结点的时候得单独讨论,此方法不适用,越界了
//由此可以理解为什么有的方法用了哨兵结点了,这样可以删除头结点
temp =tempnode->next;
tempnode->next = temp->next;
delete temp;
return head;
}
};
哨兵结点
在上面方法的基础上加入一个哨兵结点。
哨兵结点的next指向head。
(LeetCode中的head都是带数据的)
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head)//空的直接返回
{
return NULL;
}
int count = 0;//统计个数
int prev = -1;
ListNode* temp = NULL;
ListNode* tempHead = new ListNode;
ListNode* tempnode = head;
tempHead->next = head;
while(tempnode)
{
count++;
tempnode = tempnode->next;
}
tempnode = tempHead;
while(prev !=count-n)
{
prev++;
if(prev == count-n)
{
break;
}
tempnode =tempnode->next;
}
temp = tempnode->next;
tempnode->next= temp->next;
delete temp;
return tempHead->next;
}
};
快慢指针+哨兵结点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
//快慢指针都先指向新的头结点
//快指针比慢指针先走n步
//然后同时出发
//当fast走到最后一个结点时,此时slow的下一个结点就是要删除的结点
if(!head)
{
return NULL;
}
ListNode* tempHead = new ListNode;
ListNode* temp = NULL;
int count = 0;
ListNode* slow = tempHead;
ListNode* fast =tempHead;
tempHead ->next = head;
while(count != n)
{
fast = fast->next;
count++;
}
while(fast->next)
{
fast = fast->next;
slow = slow->next;
}
temp = slow->next;
slow->next = temp->next;
delete temp;
return tempHead->next;
}
};