[力扣_19] 删除链表的倒数第 N 个结点
题目入口:点击进入
相关算法:
- 双指针(快慢指针)——时间复杂度O(len),len为链表长度,空间复杂度O(1)
- 栈的应用——时间复杂度O(len+n),空间复杂度O(len)
- 暴力破解——时间复杂度O(len+n),空间复杂度O(1)
思路和算法:
这道题之所以是中等难度,是因为它多了一个附加条件:只能有一次遍历,则我们上述提供的三个解法中只有一个符合要求,那就是快慢指针
有个很重要的new技能,叫做哑结点,在未附有头结点的链表下,我们可以新增一个头结点,这样就可以对所有情况做一个统一处理,而不需要处理若删除在头端的头指针变换的特殊情况。
在本题中,我们附设一个结点,让它的next指向head。
其余两个在官方题解中能过,因为都不难,而且为了更符合题意,我们只对快慢指针做记录,其余只提供简单思路:
栈的应用——栈具有先进后出的特点,我们可以依次将结点压入栈中,然后退回到第n个结点的时候,记录下n->next结点的值,然后再退回到n的前驱,让n的前驱指向n的后继,即可完成删除,在C语言里面,需要利用动态数组的思想,对每一个压入的结点都realloc重新分配空间,实现较为麻烦。
暴力破解——我们可以先从头端出发,遍历一遍链表,得到链表长度,再从头端出发,走到n的位置,让n的前驱指向后继,完成删除。
快慢指针
快慢指针在之前线性表的题解中我们就不陌生了,快指针相当于一个侦察兵,去前端探查情况然后让慢指针依照情况进行处理
同样,我们从题意可知,我们需要找到n结点的前驱,然后让前驱指向n结点的后继,来完成删除操作,具体思路如下:
- 假设设定了双指针p和q的话,当q(快指针)达到末尾的NULL时,p与q之间相隔的元素个数为n的时候,那么删掉p的下一个指针就完成了要求
- 设立哑结点(代码中为dim)指向head
- 设定双指针p和q,初始都指向哑结点
- 移动快指针q,设立计数变量k,k随着q后移递增
- 当k>=n时候,慢指针开始移动
- 当q为空时,将p的下一个结点指向它的下下个结点
- 返回哑结点的->next(防止删除的是头结点。)
代码如下所示:
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
if(head->next==NULL&&n==1) return NULL;
struct ListNode*dim=(struct ListNode*)malloc(sizeof(struct ListNode));//哑结点
dim->next=head;
int k=0;//计数变量
struct ListNode*left=dim,*right=head;
while(right)
{
if(k>=n)//移动慢指针
left=left->next;
right=right->next;
k++;
}
left->next=left->next->next;
return dim->next;
}