[力扣_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(防止删除的是头结点。)

此图像的alt属性为空;文件名为cc43daa8cbb755373ce4c5cd10c44066dc770a34a6d2913a52f8047cbf5e6e56-file_1559548337458.gif

代码如下所示:

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;
}

本文链接:

https://nullcode.fun/65.html
1 + 8 =
快来做第一个评论的人吧~