leetcode -- 876.链表的中间节点

请添加图片描述

文章目录

- 🐨1.题目
- 🐇2. 解法1-两次遍历
- - 🍀2.1 思路
  - 🍀2.2 代码实现
- 🐁3. 解法2-快慢指针
- - 🌾3.1 思路
  - 🌾3.2 **代码实现**
- 🐮4. 题目链接

🐨1.题目

给你单链表的头结点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

🐇2. 解法1-两次遍历

🍀2.1 思路

该题没有对时间复杂度和空间复杂度作出要求，那么最直接的思路就是将链表遍历2遍：

第一次遍历：统计链表元素个数n。
第二次遍历：遍历到n/2个元素(链表首节点为第0个元素)。

🍀2.2 代码实现

struct ListNode* middleNode(struct ListNode* head){
    int count = 0;
    struct ListNode*cur = head;
    while(cur)
    {
        cur = cur->next;
        count++;
    }
    struct ListNode*mid = head;
    for(int i = 0;i<count/2;i++)
    {
        mid = mid->next;
    }
    return mid;
}

🐁3. 解法2-快慢指针

🌾3.1 思路

既然是找中间节点，那么不妨设置两个指针：

一个快指针fast，每次走2步；
一个慢指针slow，每次走1步。

那么当快指针走完的时候，慢指针正好是走到中间元素

如图所示：
我们这里需要判断结束的条件是当fast == NULL或者fast->next == NULL
请添加图片描述

🌾3.2 代码实现

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode*fast = head;
    struct ListNode*slow = head;
    //这里要先判断fast，再判断fast->next，顺序不可写反
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}