专栏首页面试经验贴[leetcode链表系列] 1 链表的中间节点

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

1 Leetcode876 链表的中间节点

给定一个带有头结点 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分钟,

效果更好哈!

01 题目解析

  • 链表简述
    • 说到链表,难免会想到数组,数组的内存地址空间连续,查找速度快(O(1)),但是插入和删除会因为大量移动元素导致效率不高,所以引入了链表结构。
    • 链表中内存低地址不连续,通过"指针"将零散的地址链接在一起,如下图(单链表)所示。
  • 解题思路(快慢指针)
    • 题中需要返回中间节点,我们使用两个指针p,q,p指针一次往前走两步,q指针一次走一步,当快指针p到达末尾也就是NULL的时候,p所指向的就是中间节点。我们看一下动画!

02 代码实现

1 c++版本

2 python版本

3 java版本

本文分享自微信公众号 - 我是程序员小贱(Lanj1995Q),作者:lj

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [leetcode链表系列]2 删除链表中的节点

    链表的一个节点是由数据域和指针域构成,指针域的地址值为下个元素的地址。那么我们需要插入或者删除一个元素怎么处理呢?

    我是程序员小贱
  • [leetcode链表系列]4 合并有序链表

    链表数据结构中哨兵的作用在之前详细阐述了[leetcode链表系列]2 删除链表中的节点,忘记了的小伙伴复习后再看效果一定翻倍哟!

    我是程序员小贱
  • [leetcode链表系列]3 链表成环

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    我是程序员小贱
  • 数据结构算法入门--链表

    数据结构算法入门系列第三篇--链表,链表也是非常常见的数据结构,面试过程中也会经常考到相关的题目。

    kbsc13
  • 学习链表,这些题你值得一刷!

    链表非常重要!虽然理论内容不多,但链表上的操作却很复杂。所以,面试中经常会考察,你一定要掌握。

    机器视觉CV
  • 《数据结构》 循环链表和双向链表常用操作代码集合

    Ps:每段代码中,添加了署名Solo的代码为博主本人所写,其余来自课本或者老师。 大量操作等同于单链表。重复的操作不再贴出,可以查看之前的博文。 循环链表 //...

    Steve Wang
  • 数据结构 | 每日一练(44)

    ——老子

    C语言入门到精通
  • 数据结构 单链表&顺序表

    顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

    Kindear
  • [日常] 链表-头结点和头指针的区别

    理解下头结点 1.头结点是为了操作的统一与方便而设立的,放在第一个元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度)。 2.有了头结点后,对在...

    陶士涵
  • [LeetCode Python 3] 876. Middle of the Linked List(链表的中间结点)

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

    Woodson

扫码关注云+社区

领取腾讯云代金券