LeetCode题解之删除链表倒数第n个结点

前言

成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都网站设计、成都网站制作、科尔沁网络推广、微信小程序、科尔沁网络营销、科尔沁企业策划、科尔沁品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联为所有大学生创业者提供科尔沁建站搭建服务，24小时服务热线：18982081108，官方网址：www.cdcxhl.com

今天继续说链表常见问题中的——删除链表倒数第n个结点：

  • 单链表反转
  • 两个有序的链表合并
  • 删除链表倒数第n个结点
  • 求链表的中间结点
  • 链表中环的检测

题目：删除链表倒数第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]

解法一

首先容易想到的办法就是想数组一样，遍历链表找到那个要被删除的结点，所以先解决两个问题：

1、获取链表的总长度

 
 
 
 
    
  
  
  
  
  1. public int getLength(ListNode head){ 
    2. 
  
  
  
  
  2.         int n=0; 
    3. 
  
  
  
  
  3.         while(head!=null){ 
    4. 
  
  
  
  
  4.             n++; 
    5. 
  
  
  
  
  5.             head=head.next; 
    6. 
  
  
  
  
  6.         } 
    7. 
  
  
  
  
  7.         return n; 
    8. 
  
  
  
  
  8.     } 
    9.

2、找到结点之后，怎么删除。

其实就是把next指向跨过去要删除的结点就行了。

 
 
 
 
    
  
  
  
  
  1. tempNode.next=tempNode.next.next; 
    2.

但是，上述这个方法是删除的tempNode.next结点，如果我们要删除tempNode本身这个结点，那么就要把一开始的结点提前到第一个结点之前。

比如我们要删除链表的第一个结点，如果你本身的指针就指向第一个结点，那么通过上面这个删除方法就永远删除不了第一个结点了。

所以要把指针提前到第一个结点之前。

所以，综上所述，我们得出以下解法：

 
 
 
 
    
  
  
  
  
  1. /** 
    2. 
  
  
  
  
  2.  * Definition for singly-linked list. 
    3. 
  
  
  
  
  3.  * public class ListNode { 
    4. 
  
  
  
  
  4.  *     int val; 
    5. 
  
  
  
  
  5.  *     ListNode next; 
    6. 
  
  
  
  
  6.  *     ListNode() {} 
    7. 
  
  
  
  
  7.  *     ListNode(int val) { this.val = val; } 
    8. 
  
  
  
  
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } 
    9. 
  
  
  
  
  9.  * } 
    10. 
  
  
  
  
  10.  */ 
    11. 
  
  
  
  
  11. class Solution { 
    12. 
  
  
  
  
  12.     public ListNode removeNthFromEnd(ListNode head, int n) { 
    13. 
  
  
  
  
  13.         int length=getLength(head); 
    14. 
  
  
  
  
  14.         //新建一个新的链表结点指向head头结点，也就是上面要注意的特殊情况 
    15. 
  
  
  
  
  15.         ListNode lastNode=new ListNode(0,head); 
    16. 
  
  
  
  
  16.         ListNode tempNode=lastNode; 
    17. 
  
  
  
  
  17.         for(int i=0;i
  
  
  
  
  18.             tempNode=tempNode.next; 
    19. 
  
  
  
  
  19.         } 
    20. 
  
  
  
  
  20.         tempNode.next=tempNode.next.next; 
    21. 
  
  
  
  
  21.         return lastNode.next; 
    22. 
  
  
  
  
  22.     } 
    23. 
  
  
  
  
  23.  
    24. 
  
  
  
  
  24.     public int getLength(ListNode head){ 
    25. 
  
  
  
  
  25.         int n=0; 
    26. 
  
  
  
  
  26.         while(head!=null){ 
    27. 
  
  
  
  
  27.             n++; 
    28. 
  
  
  
  
  28.             head=head.next; 
    29. 
  
  
  
  
  29.         } 
    30. 
  
  
  
  
  30.         return n; 
    31. 
  
  
  
  
  31.     } 
    32. 
  
  
  
  
  32. } 
    33.

时间复杂度

用到了遍历、时间复杂度为O(n)

空间复杂度

只用到几个单独的链表结点，所以空间复杂度为O(1)

解法二

再想想，可不可以不计算链表长度呢?也就是题目上所说的进阶解法，用一次扫描。

再链表中，有一种常用的方法，叫做快慢指针，意思就是用到两个速度不同的指针解决一些问题。

比如这个题中，我们使用一个快指针一个慢指针，并且让快指针快n个结点，然后两个指针一直往后移动。当快指针移动到结尾，那么慢指针的位置就是我们要删除的结点了。

当然，这里也要考虑到当前结点被删除的情况，所以要把开始结点提前到链表之前。

 
 
 
 
    
  
  
  
  
  1. public ListNode removeNthFromEnd(ListNode head, int n) { 
    2. 
  
  
  
  
  2.  //提前链表 
    3. 
  
  
  
  
  3.         ListNode LastNode=new ListNode(0,head); 
    4. 
  
  
  
  
  4.         ListNode FirstNode=LastNode; 
    5. 
  
  
  
  
  5.         ListNode SecondNode=head; 
    6. 
  
  
  
  
  6.         for(int i=0;i
  
  
  
  
  7.             SecondNode=SecondNode.next; 
    8. 
  
  
  
  
  8.         } 
    9. 
  
  
  
  
  9.  
    10. 
  
  
  
  
  10.         while(SecondNode!=null){ 
    11. 
  
  
  
  
  11.             FirstNode=FirstNode.next; 
    12. 
  
  
  
  
  12.             SecondNode=SecondNode.next; 
    13. 
  
  
  
  
  13.         } 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15.         FirstNode.next=FirstNode.next.next; 
    16. 
  
  
  
  
  16.          
    17. 
  
  
  
  
  17.         return LastNode.next; 
    18. 
  
  
  
  
  18.     } 
    19.

时间复杂度

时间复杂的为O(n)

空间复杂度

空间复杂度为O(1)

其他解法

还有其他的解法，比如用到栈先进后出的原则，先把所有链表数据入栈，然后出栈n个数。剩下的栈顶就是要删除结点的前驱结点了，然后调用上述的删除结点方法，就可以删除要删除的下个结点了。

参考

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

本文转载自微信公众号「码上积木」，可以通过以下二维码关注。转载本文请联系码上积木公众号。

名称栏目：LeetCode题解之删除链表倒数第n个结点
本文来源：http://www.gawzjz.com/qtweb2/news47/6547.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

微信公众号知识

同城分类信息

成都服务器租赁　　 　成都移动机房　　 　成都网站推广　　 　温江服务器托管　　 　成都微信二次开发公司　　 　腾讯香港免备案空间　　 　泸州叙永网站建设　　 　成都企业网站定制　　 　成都网站设计公司　　 　网站营销　　 　达州网站制作　　 　大橙子建站　　 　乐山网站建设　　 　泸州洋跃建站　　 　成都全网营销　　 　新津网站运维　　 　成都西信服务器托管　　 　成都免费做网站　　 　微信公众号二次开发　　 　商城网站