专栏首页LeetCode解题876. 链表的中间结点
原创

876. 链表的中间结点

876. 链表的中间结点

链接

链表的中间结点

给定一个带有头结点 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 和 100 之间。

解题思路

定义一个快指针fast 一个慢指针slow ,快指针一次移动两个结点,慢指针一次移动一个结点

当fast到达链表的尾部结点时,慢指针也就移动到了链表的中间结点(同化成一个路程问题,同一段路程,A的速度是B的两倍,他们同时出发,当A走完全程时,B也就刚好走过一半)

go语言版

type ListNode struct {
	Val  int
	Next *ListNode
}

func middleNode(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	return slow
}

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 876. 链表的中间结点(快慢指针)

    Michael阿明
  • [LeetCode Python 3] 876. Middle of the Linked List(链表的中间结点)

    设置两个指向头节点的快慢指针,快指针每次走两步,慢指针每次走一步,当快指针到达最后结点或为空时,慢指针指向的就是中间结点 。

    Woodson
  • 链表问题(二)-LeetCode 147、876、234、817、92(链表的中点,快慢指针)

    首先判断两个相邻节点的大小,如果head->val > head->next->val,则需要将head->next->val插入到从dummy节点开始遍历第一...

    算法工程师之路
  • LeetCode题解—求链表的中间结点

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

    码上积木
  • [leetcode链表系列] 1 链表的中间节点

    ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NU...

    我是程序员小贱
  • 2020-11-03:手写代码:链表如何快速找到中间节点?

    2.输入链表头节点,奇数长度返回中点,偶数长度返回下中点 。这道题是leetcode上的第876道题,叫【链表的中间节点】。

    福大大架构师每日一题
  • 【链表问题】删除单链表的中间节点

    以专题的形式更新刷题贴,欢迎跟我一起学习刷题,相信我,你的坚持,绝对会有意想不到的收获。每道题会提供简单的解答,如果你有更优雅的做法,欢迎提供指点,谢谢。

    帅地
  • [剑指offer] 链表中环的入口结点

    假设环长度为n,进入环之前结点个数为x,slow在环内走了k个结点,fast绕环走了m圈,则有2(x+k)=x+mn+k 可以得出x = mn - k。此时sl...

    尾尾部落
  • [剑指offer] 链表中倒数第k个结点 [剑指offer] 链表中倒数第k个结点

    经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

    尾尾部落

扫码关注云+社区

领取腾讯云代金券