阿裡面試真題詳解：帶環連結清單 II

描述

給定一個連結清單，如果連結清單中存在環，則傳回到連結清單中環的起始節點，如果沒有環，傳回null。

線上評測位址：

領扣題庫官網

輸入：null,no cycle
輸出：no cycle
解釋：
連結清單為空，是以沒有環存在。           

樣例2
輸入：-21->10->4->5，tail connects to node index 1
輸出：10
解釋：
最後一個節點5指向下标為1的節點，也就是10，是以環的入口為10。           

算法思路：

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up: Can you solve it without using extra space?

考點：

• 雙指針連結清單判環

  題解：

• 使用雙指針判斷連結清單中是否有環，慢指針每次走一步，快指針每次走兩步，若連結清單中有環，則兩指針必定相遇。
• 假設環的長度為l，環上入口距離連結清單頭距離為a，兩指針第一次相遇處距離環入口為b，則另一段環的長度為c=l-b，由于快指針走過的距離是慢指針的兩倍，則有a+l+b=2*(a+b),又有l=b+c，可得a=c，故當判斷有環時(slow==fast)時，移動頭指針，同時移動慢指針，兩指針相遇處即為環的入口。

  /**
  * Definition for ListNode.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int val) {
  *         this.val = val;
  *         this.next = null;
  *     }
  * }
  */            

  public class Solution {
  public ListNode detectCycle(ListNode head) {
      if (head == null || head.next==null) {
          return null;
      }
  
      ListNode fast, slow;
      fast = head.next;                        //快指針
      slow = head;                                //慢指針
      while (fast != slow) {                //快慢指針相遇
          if(fast==null || fast.next==null)
              return null;
          fast = fast.next.next;
          slow = slow.next;
      } 
  
      while (head != slow.next) {  //同時移動head和慢指針
          head = head.next;
          slow = slow.next;
      }
      return head;                                //兩指針相遇處即為環的入口
  }
  }           

  更多題解參考：九章官網solution