「LeetCode」876-链表的中间结点⚡️

简介: 「LeetCode」876-链表的中间结点⚡️

image.png

前言🌧️


算法,对前端人来说陌生又熟悉,很多时候我们都不会像后端工程师一样重视这项能力。但事实上,算法对每一个程序员来说,都有着不可撼动的地位。


因为开发的过程就是把实际问题转换成计算机可识别的指令,也就是《数据结构》里说的,「设计出数据结构,在施加以算法就行了」。


编写指令的好坏,会直接影响到程序的性能优劣,而指令又由数据结构和算法组成,所以数据结构和算法的设计基本上决定了最终程序的好坏


题目🦀



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,我们返回第二个结点。

提示:

  • 给定链表的结点数介于 1100 之间。


解题思路🌵



  • 采用双指针解题
  • 我们可以快指针每次走两步,慢指针每次走一步
  • 这样最后快指针走完时,慢指针刚好就能走到中间


解题步骤🐂


  • 初始化左右指针
  • 循环遍历
  • 返回左指针

源码🔥


/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let left=head;
    let right=head;
    while(right && right.next){
        left=left.next
        right=right.next.next
    }
    return left
};

时间复杂度:O(nlogn)


空间复杂度:O(1)


结束语🌞


image.png

那么鱼鱼的LeetCode算法篇的「LeetCode」876-链表的中间结点⚡️ 就结束了,算法这个东西没有捷径,只能多写多练,多总结,文章的目的其实很简单,就是督促自己去完成算法练习并总结和输出,菜不菜不重要,但是热爱🔥,喜欢大家能够喜欢我的短文,也希望通过文章认识更多志同道合的朋友,如果你也喜欢折腾,欢迎加我好友,一起沙雕,一起进步


相关文章
|
1天前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
1天前
|
机器学习/深度学习
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13:在 O(1) 时间删除链表结点
|
2天前
|
C语言 C++ 索引
力扣 138. 随机链表的复制
力扣 138. 随机链表的复制
|
3天前
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
8 1
|
8天前
LeetCode链表hard 有思路?但写不出来?
LeetCode链表hard 有思路?但写不出来?
|
8天前
|
索引
每日一题:力扣328. 奇偶链表
每日一题:力扣328. 奇偶链表
15 4
|
8天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
12 0
|
8天前
19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——反转链表
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点

热门文章

最新文章