【力扣刷题实战】链表的中间结点

大家好，我是小卡皮巴拉

文章目录

目录

力扣题目：链表的中间结点

题目描述

示例 1：

示例 2：

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码（C语言）

兄弟们共勉！！！ 

---

每篇前言

博客主页：小卡皮巴拉

咱的口号：🌹小比特，大梦想🌹

作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。

 

力扣题目：链表的中间结点

原题链接：链表的中间结点

题目描述

给你单链表的头结点 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 ，返回第二个结点。

解题思路

问题理解

题目要求找出并返回给定单链表的中间结点。如果链表长度为偶数，存在两个中间结点，则返回靠后的那一个（即第二个中间结点）。

算法选择

使用快慢指针算法。快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾（fast == NULL 或 fast->next == NULL）时，慢指针恰好到达链表的中间位置。

具体思路

1. 初始化快慢指针：

   • ListNode* slow = head;

   • ListNode* fast = head;

2. 处理空链表情况：

   • 如果链表为空（head == NULL），则直接返回空指针（虽然题目没有明确指出空链表的情况，但为了代码的健壮性，我们进行此处理）。

3. 使用快慢指针遍历链表：

   • 进入 while 循环，循环条件是 fast 和 fast->next 都不为空。这是为了确保快指针在移动两步时不会越界。

   • 在循环内部，慢指针 slow 每次移动一步（slow = slow->next;）。

   • 快指针 fast 每次移动两步（fast = fast->next->next;）。

4. 返回结果：

   • 当快指针到达链表末尾（即 fast == NULL 或由于 fast->next 为空而退出循环）时，慢指针 slow 恰好指向链表的中间结点。

   • 返回慢指针所指向的结点（return slow;）。

解题要点

• 快慢指针的初始化：确保快慢指针都指向链表的头结点。

• 空链表的处理：检查链表是否为空。

• 循环条件的设置：确保快指针在移动两步时不会越界，即需要同时检查 fast 和 fast->next 是否为空。且(fast && fast->next)的顺序不能改变。

  因为调换后可能会对空指针fast进行解引用操作，是错误的

  而这种写法可以使用是因为能发生短路

  当fast为空指针时，该条件就不会再向后判断了，就不会发生对空指针的解引用

• 指针的移动：在循环内部，慢指针每次移动一步，快指针每次移动两步。

• 返回结果：当快指针到达链表末尾时，返回慢指针所指向的结点，即为链表的中间结点。

完整代码（C语言）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) 
{
    //定义快慢指针
    ListNode* slow = head;
    ListNode* fast = head;
    //空链表单独处理
    if(head == NULL)
    {
        return head;
    }
    //分为奇数和偶数两种情况
    //奇数：fast->next = NULL终止
    //偶数：fast = NULL终止
    //两种情况任一不满足，都不能进入循环，是&&
    while(fast && fast->next)//不能调换位置！
    //因为调换后可能会对空指针fast进行解引用操作，是错误的
    //这种写法可以使用是因为能发生短路
    //当fast为空指针时，该条件就不会再向后判断了，就不会发生对空指针的解引用
    {
        slow = slow->next;
        fast = fast->next->next;
    }  
    return slow;
}

兄弟们共勉！！！ 

码字不易，求个三连

抱拳了兄弟们！

 

原文地址：https://blog.csdn.net/2401_85548793/article/details/142941449

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！