【前言】

今天是刷题打卡第46天！

...词穷了，总之加油鸭。

原题：环形链表（双指针）

示例1：

  

   

    

     

    
    

     

      输入：head = [3,2,0,-4], pos = 1
     
    
   

    

     

    
    

     

      输出：true
     
    
   

    

     

    
    

     

      解释：链表中有一个环，其尾部连接到第二个节点。
     
    
  
 

 示例2：

  

   

    

     

    
    

     

      输入：head = [1], pos = -1
     
    
   

    

     

    
    

     

      输出：false
     
    
   

    

     

    
    

     

      解释：链表中没有环。
     
    
  
 

思路（快慢指针）：

很简单，利用快慢指针来做就行了，如果链表有环，那么slow和fast一定会相遇。

代码执行：

  

   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * Definition for singly-linked list.
     
    
   

    

     

    
    

     

       * struct ListNode {
     
    
   

    

     

    
    

     

       * int val;
     
    
   

    

     

    
    

     

       * struct ListNode *next;
     
    
   

    

     

    
    

     

       * };
     
    
   

    

     

    
    

     

       */
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool hasCycle(struct ListNode *head) {
     
    
   

    

     

    
    

     
    struct ListNode* slow = head;
     
    
   

    

     

    
    

     
    struct ListNode* fast = head;
     
    
   

    

     

    
    

     

          这里添加fast->next目的是防止空指针异常，因为循环体内fast一次走两步
     
    
   

    

     

    
    

     
    while(fast && fast->next)//之所以加上fast->next!=NULL这个条件，防止越界访问导致空指针异常
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              slow = slow->next;
     
    
   

    

     

    
    

     

              fast = fast->next->next;
     
    
   

    

     

    
    

     
        if(slow == fast)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            return true;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    return false;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

结语

今天是刷题打卡第46天！

加油吧少年。

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

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