链表的中间结点——每日一题

题目链接：

OJ链接




 

题目：

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

理解分享：

我采用了快慢指针的方法来实现。

首先，我们定义了两个指针 n1 和 n2，它们都初始化为指向链表的头节点 head。

然后，我们进入一个循环，条件是 n2 不为空且 n2 的下一个节点也不为空。在循环的每一次迭代中，n1 指针每次移动一步，而 n2 指针每次移动两步。这样做的效果是，当 n2 指针到达链表的末尾时，n1 指针恰好处于链表的中间位置。

最后，我们返回 n1 指针所指向的节点，即链表的中间节点。

这种方法的关键在于，通过使用两个指针，一个指针移动速度为另一个指针的两倍，当快指针到达链表尾部时，慢指针正好处于链表的中间位置，从而实现了在一次遍历中找到链表的中间节点。这种算法的时间复杂度是 O(n)，其中 n 是链表的长度。

代码：

typedef struct ListNode ll;
 
// 找到链表的中间节点
struct ListNode* middleNode(struct ListNode* head) {
    // 定义两个指针，初始都指向头节点
    ll* n1 = head;  // 慢指针
    ll* n2 = head;  // 快指针
    
    // 当快指针不为空且快指针的下一个节点也不为空时，继续循环
    while (n2 && n2->next) {
        // 慢指针每次向后移动一步
        n1 = n1->next;
        // 快指针每次向后移动两步
        n2 = n2->next->next;
    }
    
    // 当快指针到达链表末尾时，慢指针指向的节点即为链表的中间节点
    return n1;
}