【前言】

今天是刷题打卡第45天！

2021还有20来天就要结束咯，时间过得真是快鸭。

原题：链表的中间节点（双指针）

示例1：

  

   

    

     

    
    

     

      输入：[1,2,3,4,5]
     
    
   

    

     

    
    

     

      输出：此列表中的结点 3 (序列化形式：[3,4,5])
     
    
   

    

     

    
    

     

      返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
     
    
   

    

     

    
    

     

      注意，我们返回了一个 ListNode 类型的对象 ans，这样：
     
    
   

    

     

    
    

     

      ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
     
    
  
 

 示例2：

  

   

    

     

    
    

     

      输入：[1,2,3,4,5,6]
     
    
   

    

     

    
    

     

      输出：此列表中的结点 4 (序列化形式：[4,5,6])
     
    
   

    

     

    
    

     

      由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
     
    
  
 

思路（快慢指针）：

本题采用“快慢指针”解决，慢指针一次走一步，快指针一次走两步，不过需要注意的是本题受到节点总数是奇偶的影响，当节点总数是奇数时，fast->next == NULL，slow就指向了中间结点；当节点总数是偶数时，fast == NULL，slow就指向了中间结点，所以循环条件有两个，但是循环条件的先后顺序也是有讲究的，不信你看代码。

代码执行：

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * struct ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * struct ListNode *next;
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      struct ListNode* middleNode(struct ListNode* head){
     
    
   

    

     

    
    

     
    //两个指针的起始位置都是从头开始
     
    
   

    

     

    
    

     
    struct ListNode* slow = head;
     
    
   

    

     

    
    

     
    struct ListNode* fast = head;
     
    
   

    

     

    
    

     
    //注意循环条件不能写成fast->next && fast这种形式，原因在于fast走两步后可能就指向空了
     
    
   

    

     

    
    

     
    //再执行循环条件fast->next会导致空指针异常，越界了,但是fast写在前面就不会出现上述情况，因为&&存在短路求值
     
    
   

    

     

    
    

     
    while(fast && fast->next)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              slow = slow->next;//slow每次走一步
     
    
   

    

     

    
    

     

              fast = fast->next->next;//fast每次走两步
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return slow;//此时slow就指向中间节点
     
    
   

    

     

    
    

     

      }
     
    
  
 

结语

今天是刷题打卡第45天！

加油吧少年。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121842876