C语言每日一题（42）删除链表的倒数第N个结点
C语言每日一题（42）删除链表的倒数第N个结点
题目描述
给你一个链表，删除链表的倒数第 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]提示：
- 链表中结点的数目为
sz 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
思路分析
关于这道题，有两种思路和三种不同的方法，我们来一一分析。
思路1：快慢指针法
我们之前做过一题，找出链表的倒数第N个结点，我们可以在此基础上进行，找到第N个结点，然后删除即可，但这里涉及到一些特殊情况：
1.当链表长度只有一个，且n=1时，如果直接释放头结点的话会野指针；
2.当需要删除的结点是头结点，直接删除的话会丢失后面的结点。
这里分成两种方法进行实现：
1.带一个哨兵位
我们发现，往往与删除功能有关的题都会需要考虑链表为空的情况，但只要定义一个哨兵位指向头结点就能很好解决，减少代码量，提供效率。
有了哨兵位，删除也方便了许多。我们通过快慢指针法遍历链表，得到slow指向的结点就是需要删除的结点，但此时还得需要获得它的前驱结点，这时就得定义第三个指针在遍历的时候指向它的前驱结点，且又得考虑链表为空的情况（在方法2不带哨兵位会进行解释）但如果有了哨兵位，我们可以让快指针从头结点开始，二慢指针从哨兵位开始，遍历结束后，slow指针的下一个就是要删除的结点，相当于不找删除结点，而是找删除结点的前驱结点，直接指向下一个结点的下一个完成删除。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位，不存储有效数据，用来解决链表为空的情况
dummy->val=0;
dummy->next=head;
struct ListNode* fast=head;//快指针
struct ListNode* slow=dummy;//慢指针
while(n--)
{
if(fast==NULL)
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;
struct ListNode* ans=dummy->next;
free(dummy);//动态开辟的空间记得释放
return ans;
}2.不带哨兵位
有些小伙想要锻炼自己的代码能力，一般是不喜欢用哨兵位，貌似有点投机取巧的感觉（作者本人是这么想的。。。），下面我们来介绍一下不带哨兵位的做法。
既然不带哨兵位，我们就需要第三个指针在遍历时保存删除结点的前驱结点，同时链表为空和头结点为野指针的情况要逐一考虑。
当我们需要删除的结点是头结点，就需要将head指针移动到下一个当作新的头结点再将原来的结点释放。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode* fast=head;
struct ListNode* slow=head;
struct ListNode* prev=head;
while(n--)
{
if(fast==NULL)
{
return NULL;
}
fast=fast->next;
}
while(fast)
{
prev=slow;
slow=slow->next;
fast=fast->next;
}
if(slow==head)
{
head=slow->next;
free(slow);
}
else
{
prev->next=slow->next;
free(slow);
}
return head;
}思路2：链栈
这是力扣官方的一个解题思路，只需要遍历一次即可。
步骤就是将链表的所有元素入栈，根据n的值来决定出栈的次数，出栈完后，会发现此时栈顶元素就是需要删除结点的前驱结点，之后进行删除。
链表入栈的方式和链表的头插是类似的，为了增加效率，我们带一个哨兵位（嘻嘻）。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct Stack//链栈类
{
struct ListNode* val;//存储的元素类型是链表
struct Stack* next;//指向下一个栈类
};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode));//哨兵位初始化
dummy->val=0;
dummy->next=head;
struct ListNode* cur=dummy;
struct Stack* stk=NULL;
while(cur)//入栈
{
struct Stack* tmp=(struct Stack*)malloc(sizeof(struct Stack));//基于头插法实现
tmp->val=cur;
tmp->next=stk;
stk=tmp;
cur=cur->next;
}
while(n--)//出栈
{
struct Stack* tmp=stk->next;
free(stk);
stk=tmp;
}
struct ListNode* prev=stk->val;//栈顶元素就是删除元素的前驱结点
prev->next=prev->next->next;//进行删除
struct ListNode* ans=dummy->next;//释放开辟的哨兵位
free(dummy);
return ans;
}腾讯云开发者
