前言
没错,今天又是算法,马上放假啦,心已经飞走了。
今天继续说说链表算法题:求链表的中间结点。
题目:求链表的中间结点
给定一个头结点为 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
上面的例子就是快慢指针会走到的节点数:
时间复杂度
用到了遍历,所以时间复杂度还是O(n)
空间复杂度
空间复杂度为O(1)
其他解法
如果该题是数组的话,是不是一句代码就能解出来呢?Array[n/2]。所以我们完全可以将链表转化成数组,然后一句代码就可以输出中间结点数了,你可以动手试试哦。
这种解法的时间复杂度和空间复杂度又是多少呢?
参考
https://leetcode-cn.com/problems/middle-of-the-linked-list/
本文转载自微信公众号「码上积木」,可以通过以下二维码关注。转载本文请联系码上积木公众号。
背景 我们知道 如果在Kubernetes中支持GPU设备调度 需要做如下的工作 节点上安装...
TIOBE 公布了 2021 年 3 月的编程语言排行榜。 本月 TIOBE 指数没有什么有趣的变...
本文转载自微信公众号「bugstack虫洞栈」,作者小傅哥 。转载本文请联系bugstack...
本文转载自公众号读芯术(ID:AI_Discovery)。 这一刻你正在应对什么挑战?这位前...
在Python开发过程中,我们难免会遇到多重条件判断的情况的情况,此时除了用很多...
想了解更多内容,请访问: 51CTO和华为官方战略合作共建的鸿蒙技术社区 https://...
基本介绍 给定 n 个权值作为 n 个叶子节点,构造一颗二叉树,若该树的带权路径长...
溢价 域名 的续费价格如何?通常来说,因为溢价域名的价值高于普通域名,所以溢...
前言 统计科学家使用交互式的统计工具(比如R)来回答数据中的问题,获得全景的认...
近几年,互联网行业蓬勃发展,在互联网浪潮的冲击下,互联网创业已成为一种比较...