[leetcode链表系列] 1 链表的中间节点

2020/11/01 10:42
阅读数 18


38c53560cb92b4175dee204888fee2fc.gif

1Leetcode876 链表的中间节点

给定一个带有头结点 head 的非空单链表,返回链表的中间结点。

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



输入:[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分钟,

效果更好哈!


0 1题目解析

  • 链表简述

    • 说到链表,难免会想到数组,数组的内存地址空间连续,查找速度快(O(1)),但是插入和删除会因为大量移动元素导致效率不高,所以引入了链表结构。

    • 链表中内存低地址不连续,通过"指针"将零散的地址链接在一起,如下图(单链表)所示。

fc28bfeea1b42510f02d65c5df57c135.png

  • 解题思路(快慢指针)

    • 题中需要返回中间节点,我们使用两个指针p,q,p指针一次往前走两步,q指针一次走一步,当快指针p到达末尾也就是NULL的时候,p所指向的就是中间节点。


0 2   代码实现

1 c++版本

c87e73aa9bfd05b7458b4909fd0e622c.jpeg

2 python版本

f3cf39976a887c65ec26c917e335a6e2.jpeg

3  java版本

a148f73876fad283f9c1a4344f704bfc.jpeg












展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部