《手撕链表题系列-3》找到链表的中间结点

前言

本系列主要讲解链表的经典题

注：划重点！！必考~

找到链表的中间结点

力扣链接：876. 链表的中间结点 - 力扣（LeetCode） (leetcode-cn.com)

• 题目描述：

给定一个头结点为 head 的非空单链表，返回链表的中间结点

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

• 示例：

• 提示：

• 给定链表的结点数介于 1 和 100 之间

• 解题思路：

• 一般的思路：

一个个遍历，得到链表长度，在遍历链表长度的二分之一，就能得到中间结点

• 高效思路：

1. 使用两个指针
2. 一个慢指针每次走一个结点的位置
3. 一个快指针每次走慢指针的两倍长度
4. 当快指针走完链表时，而慢指针则恰在链表中间结点位置

注意：链表长度有奇数和偶数两种情况

注：这里我们来实现高效思路

图示：

• 参考代码：

1.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    //创建快慢指针，快指针走两步，而慢指针走一步（当快指针到尾时，慢指针在中间）
    struct ListNode*slow,*fast;
    slow=fast=head;
    //节点为单数时，快指针走到尾节点（fast下一个节点为NULL则停止）
    //节点为双数时，快指针走到尾节点的下一个节点NULL（fast为NULL则停止）
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

• 结果：

每日k题无烦恼，点赞学习不得了~