LeetCode题解之求链表的中间结点

前言

创新互联是一家专注网站建设、网络营销策划、微信小程序定制开发、电子商务建设、网络推广、移动互联开发、研究、服务为一体的技术型公司。公司成立十余年以来，已经为1000+汽车玻璃修复各业的企业公司提供互联网服务。现在，服务的1000+客户与我们一路同行，见证我们的成长；未来，我们一起分享成功的喜悦。

没错，今天又是算法，马上放假啦，心已经飞走了。

今天继续说说链表算法题：求链表的中间结点。

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

题目：求链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：输入：[1,2,3,4,5] 输出：此列表中的结点 3

(序列化形式：[3,4,5]) 返回的结点值为 3 。

(测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样：ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：输入：[1,2,3,4,5,6] 输出：此列表中的结点 4

(序列化形式：[4,5,6])

由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

解法一

题目意思还是比较简单的，就是找到中间结点。

首先想到的就是先算出来链表总长度，然后再遍历到中间结点就可以了：

 
 
 
 
      
  
  
  
  1. public ListNode middleNode(ListNode head) { 
    2.   
  
  
  
  2.         int n = 0; 
    3.   
  
  
  
  3.         ListNode cur = head; 
    4.   
  
  
  
  4.         while (cur != null) { 
    5.   
  
  
  
  5.             n++; 
    6.   
  
  
  
  6.             cur = cur.next; 
    7.   
  
  
  
  7.         } 
    8.   
  
  
  
  8.         int k = 0; 
    9.   
  
  
  
  9.         cur = head; 
    10.   
  
  
  
  10.         while (k < n / 2) { 
    11.   
  
  
  
  11.             k++; 
    12.   
  
  
  
  12.             cur = cur.next; 
    13.   
  
  
  
  13.         } 
    14.   
  
  
  
  14.         return cur; 
    15.   
  
  
  
  15.     } 
    16.

时间复杂度

一共遍历了1次加半次。去除常量，时间复杂度为O(n)

空间复杂度

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

解法二

还记得上一篇我们说到的找到结尾第n个结点算法题吗?其中用到了一个叫做快慢指针的解法。

在这里依然可以用到。可能你就有疑惑了，上一次是知道两个指针之间相隔n个结点，这一次怎么用呢?

如果我们将慢指针每次移动一格，快指针每次移动两格，那么快指针是不是每次都是慢指针的两倍步数呢?

这样当快指针移到尾部的时候，慢指针就刚好在中间结点了。

 
 
 
 
      
  
  
  
  1. public ListNode middleNode(ListNode head) { 
    2.   
  
  
  
  2.         ListNode slow = head; 
    3.   
  
  
  
  3.         ListNode fast = head; 
    4.   
  
  
  
  4.         while (fast != null && fast.next != null) { 
    5.   
  
  
  
  5.             slow = slow.next; 
    6.   
  
  
  
  6.             fast = fast.next.next; 
    7.   
  
  
  
  7.         } 
    8.   
  
  
  
  8.         return slow; 
    9.   
  
  
  
  9.     } 
    10.

这里因为每次fast都要移动两步，所以需要判断当前结点和下一个结点是否都为空。

 
 
 
 
      
  
  
  
  1. slow 1  2  3  4  5  6   
    2.   
  
  
  
  2. fast 1  3  5  7  9  11   
    3.

上面的例子就是快慢指针会走到的节点数：

  • 如果链表为奇数，比如[1,2,3,4,5]，那么刚好快慢结点就会走到3和5。
  • 如果链表为奇数，比如[1,2,3,4,5,6]，那么刚好快慢结点就会走到4和null。

时间复杂度

用到了遍历，所以时间复杂度还是O(n)

空间复杂度

空间复杂度为O(1)

其他解法

如果该题是数组的话，是不是一句代码就能解出来呢?Array[n/2]。所以我们完全可以将链表转化成数组，然后一句代码就可以输出中间结点数了，你可以动手试试哦。

这种解法的时间复杂度和空间复杂度又是多少呢?

参考

https://leetcode-cn.com/problems/middle-of-the-linked-list/

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

网页题目：LeetCode题解之求链表的中间结点
地址分享：http://www.shufengxianlan.com/qtweb/news38/239288.html

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

广告

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

猜你还喜欢下面的内容

网页设计公司知识

同城分类信息

吉安网站建设　　 　机柜租用　　 　雨棚定制　　 　成都网站设计制作公司　　 　橡塑保温板　　 　成都营销网站制作　　 　攀枝花网站建设　　 　平武做网站　　 　公司logo设计　　 　网站优化公司　　 　重庆企业网站建设　　 　成都企业网站维护　　 　泸州网站建设　　 　重庆服务器托管　　 　温江电信机房　　 　成都网站推广　　 　重庆网站制作　　 　品牌网站定制　　 　成都app软件开发　　 　移动服务器托管