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

题目要求

链接: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;
 * };
 */

  //从头开始统计链表长度  
    struct ListNode* 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) 可能存在对空指针解引用情况

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

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

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

在这里插入图片描述
在这里插入图片描述



本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>