Leetcode:876. 链表的中间结点【详解】

迷南。 2024-02-20 12:20 37阅读 0赞

**目录**

题目

题目解析：

代码展示

图解

### **题目** ###

> **给你单链表的头结点 `head` ，请你找出并返回链表的中间结点。**
> 
> **如果有两个中间结点，则返回第二个中间结点。**
> 
> 难度：简单
> 
> **题目链接**：[876. 链表的中间结点][876.]

![ee871ef195d149088d310c79baa2d884.png][]

**提示：**

*  链表的结点数范围是 `[1, 100]`
 *  `1 <= Node.val <= 100`

### **题目解析：** ###

**题目给出的链表结点的存储**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */

由题目可以知道，题目要求返回中间的结点。

*  方法1：**两次遍历指针**，第一遍遍历计算结点个数(奇数个还是偶数个)，第二遍去查找中间结点并返回。  
    
 *  方法2：使用**快慢指针**来控制(只需遍历一遍链表即可) ，当快指针走两步，慢指针走一步。当快指针走到最后一个结点，或者走到NULL。即遍历完一遍指针。返回慢指针指向的结点。

### **代码展示** ###

**方法1 ：**

struct ListNode* middleNode(struct ListNode* head){
        struct ListNode * pl = head;
        int i = 0;
        //遍历第一遍
        while(pl != NULL)
        {
            pl = pl->next;
            i++;
        }
        //第二次遍历
        int t = i/2;
        while(t--)
        {
            head = head->next;
        }
        return head;
        
    }

#### **图解**   ![70f91c79a71243508ffac39ff32681e6.png][] ####

**方法二：**

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* middleNode(struct ListNode* head){
        //先让快慢指针指向头结点
        struct ListNode *low = head, *fast = head;
        while(fast && fast->next)
        {
            low = low->next;    //下一个节点
            fast = fast->next->next; //下一个节点的节点
        }
    
        return low;    //返回慢指针，指向的节点
        
    }

这里的 fast&&fast->next 表示 fast不是空指针或者fast的下一个节点不是空，就执行while循环中的语句。

**图解：**

**第一步**，起初都指向第一个结点

![88587414f01d47748994cd2982f26b72.png][]

**第二步**，进行遍历。慢指针走一步，快指针走两步。

![55e1f48c65a94e9bbe3aa589f06e1954.png][]

**第三步**，遍历完成。当快指针指到最后一个结点 或者 指向NULL时；此时的low指针指的结点就是中间结点。

奇数个结点

![85ead73362aa48ee90e61c1721685ae5.png][]

偶数个结点的情况

![a627e792e74b4ad9a3440ef74272a9fa.png][]

[876.]: https://leetcode.cn/problems/middle-of-the-linked-list/description/
[ee871ef195d149088d310c79baa2d884.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/ec77c9fe43d0430aa6f0bebb762ae9a9.png
[70f91c79a71243508ffac39ff32681e6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/433ae742abdf4a2c966439d43a8ac0d8.png
[88587414f01d47748994cd2982f26b72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/526c76133505458ebebdf332a9e1279d.png
[55e1f48c65a94e9bbe3aa589f06e1954.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a7dce41381e6451e9a3b780fa7c025f6.png
[85ead73362aa48ee90e61c1721685ae5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/4d38f4728f3e49fd995e8a92569c91e1.png
[a627e792e74b4ad9a3440ef74272a9fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a25a5f8754ea47e89425f4ab5dd58c38.png