舍友仅仅打了一把游戏，我就学会了如何找链表的中间结点

文章目录

题目要求

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

方法1：统计长度 走两遍

思路：

• 第一步：从头遍历一遍链表得出链表的长度，记为size
• 第二步:从头开始走，走 mid = size/2步 就是链表的中间结点whle( mid--)==>这样是循环mid次while(--mid)==>这样是循环mid-1次
• 无论是奇数个结点还是偶数个结点都合适

图解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 *///从头开始统计链表长度  structListNode* cur = head;int size =0;while(cur){
        size++;
        cur = cur->next;}//从头开始重新遍历，走长度的一半步
    cur = head;int mid = size /2;//走mid步while(mid--){
        cur = cur->next;}//走完mid步，cur指向的就是中间结点return cur;}

方法2：快慢指针

思路

• 定义两个指针，一个fast 一个slow
• 二者从头开始遍历 fast走两步 slow走一步- fast = fast -> next -> next- slow = slow ->next
• 奇数个结点结束条件：fast 走到尾结点 (fast ->next NULL)

• 偶数个结点结束条件：fast走到空 (fast == NULL)

因为不知道结点个数是奇数个还是偶数个

所以循环条件可写成

while(fast && fast ->next )  
 当fast走到NULL 或者 fast->next为空时，&&发生短路，跳出循环
    
//不可写成 while(fast->next && fast) 可能存在对空指针解引用情况

structListNode*middleNode(structListNode* head){//定义快慢指针structListNode* fast = head;structListNode* slow = head;while(fast && fast->next){//快指针走两步
      fast = fast->next->next;//慢指针走一步
      slow = slow ->next;}return slow;}

易错点：while判断中： fast->next 和fast 顺序

//errwhile(fast->next && fast){//快指针走两步
      fast = fast->next->next;//慢指针走一步
      slow = slow ->next;}