力扣876:链表的中间结点

简介: 力扣876:链表的中间结点

力扣876:链表的中间结点

题目描述:

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

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

示例 1:

输入:head = [1,2,3,4,5]

输出:[3,4,5]

解释:链表只有一个中间结点,值为 3 。

示例 2:

输入:head = [1,2,3,4,5,6]

输出:[4,5,6]

解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。

提示:

链表的结点数范围是 [1, 100]

1 <= Node.val <= 100

分析:

快慢指针思想

定义两个指针,快指针fast,慢指针slow,从头开始遍历:

fast一次走两步,慢指针一次走两步

遍历结束后,慢指针所在的节点就是中间节点,返回slow即可

那么什么时候遍历结束呢?

链表为奇数个时:

fast->next为空时,遍历结束。

链表为偶数个时:

fast为空时,遍历结束。

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode*fast=head,*slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}
目录
相关文章
|
12天前
19 删除链表的倒数第 N 个结点
19 删除链表的倒数第 N 个结点
|
1月前
|
算法
LeetCode刷题---21.合并两个有序链表(双指针)
LeetCode刷题---21.合并两个有序链表(双指针)
|
1月前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
1月前
|
算法 测试技术
LeetCode刷题--- 430. 扁平化多级双向链表(深度优先搜索)
LeetCode刷题--- 430. 扁平化多级双向链表(深度优先搜索)
|
1月前
|
存储
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
实现单链表的基本操作(力扣、牛客刷题的基础&笔试题常客)
140 38
|
4天前
【力扣】21. 合并两个有序链表
【力扣】21. 合并两个有序链表
|
1月前
|
存储 JavaScript
leetcode82. 删除排序链表中的重复元素 II
leetcode82. 删除排序链表中的重复元素 II
22 0
|
1月前
leetcode83. 删除排序链表中的重复元素
leetcode83. 删除排序链表中的重复元素
10 0
|
1月前
leetcode2807.在链表中插入最大公约数
leetcode2807.在链表中插入最大公约数
16 0