LeetCode题解之怎么求链表的中间结点
更新:HHH   时间:2023-1-7


本篇内容介绍了“LeetCode题解之怎么求链表的中间结点”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

题目:求链表的中间结点

给定一个头结点为 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,我们返回第二个结点。

解法一

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

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

public ListNode middleNode(ListNode head) {         int n = 0;         ListNode cur = head;         while (cur != null) {             n++;             cur = cur.next;         }         int k = 0;         cur = head;         while (k < n / 2) {             k++;             cur = cur.next;         }         return cur;     }

时间复杂度

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

空间复杂度

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

解法二

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

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

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

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

public ListNode middleNode(ListNode head) {         ListNode slow = head;         ListNode fast = head;         while (fast != null && fast.next != null) {             slow = slow.next;             fast = fast.next.next;         }         return slow;     }

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

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

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

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

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

“LeetCode题解之怎么求链表的中间结点”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注天达云网站,小编将为大家输出更多高质量的实用文章!

返回web开发教程...