剑指Offer_23_链表中环的入口节点

❗️LeetCode_141_环形链表、LeetCode_142_环形链表2

题目描述：

如果一个链表中包含环，如何找出环的入口节点？

解法1：快慢指针（Floyd判圈法）

1. 第一步是如何确定一个链表中包含环并返回两个指针相遇的节点，受到面试题22的启发，我们可以用两个指针来解决这个问题：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走的慢的指针，那么链表就包含环，如果走的快的指针走到了链表的末尾都没有追上第一个指针，那么链表就不包含环

   /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
    * };
    */
   class Solution {
   public:
     
       //该函数返回两个指针相遇的节点
       ListNode* MeetingNode(ListNode *head) {
           
           if (head == NULL) return NULL;
   
           ListNode* slow = head;  //定义慢指针
           ListNode* fast = head;  //定义快指针
   
           if (slow->next == NULL) return NULL;  //如果链表中只有一个节点，那就没有环
   
           while (fast != NULL && fast->next != NULL) {
   
               fast = fast->next->next;
               slow = slow->next;
   
               if (fast == slow) return fast;  //fast或slow指针指向的节点就是它们相遇的节点
           }
   
           return NULL;
   
       }
   };

2. 第二步是如何找到环的入口节点

   /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
    * };
    */
   class Solution {
   public:
       ListNode *detectCycle(ListNode *head) {
           
           if (head == NULL) return NULL;
   
           ListNode* slow = head;  //定义慢指针
           ListNode* fast = head;  //定义快指针
           bool hasCycle = false;
   
           if (slow->next == NULL) return NULL;  //如果链表中只有一个节点，那就没有环
   
           while (fast != NULL && fast->next != NULL) {
   
               fast = fast->next->next;
               slow = slow->next;
   
               //fast或slow指针指向的节点就是它们相遇的节点
               if (fast == slow) {
   
                   hasCycle = true;  //该链表有环
                   break;  //跳出循环
               }
           }
   
           //如果有环，找到入环开始的结点
           if (hasCycle) {
   
               ListNode *p = head;
               while (p != slow) { 
   
                   p = p ->next;
                   slow = slow->next;
               }
               return p;  //p指针指向的节点就是环的入口节点
           } else return NULL;
       }
   };

   //代码更简洁
   
   /**
    * Definition for singly-linked list.
    * struct ListNode {
    *     int val;
    *     ListNode *next;
    *     ListNode(int x) : val(x), next(NULL) {}
    * };
    */
   class Solution {
   public:
       ListNode *detectCycle(ListNode *head) {
   
           ListNode* slow = head,*fast = head;
   
           //判断是否存在环路
           do {
   
               if (fast == NULL || fast->next == NULL) return NULL;
               fast = fast->next->next;
               slow = slow->next;
           } while (fast != slow);
   
           //如果存在，查找环路节点
           fast = head;
           while (fast != slow) {
               slow = slow->next;
               fast = fast->next;
           }
   
           return fast;
       }
   };