java給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null

文章目錄

• • 問題描述
  • 思路
  • 圖解
  • 代碼

問題描述

給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null

思路

快慢指針法，快指針每次走兩步，慢指針每次走一步。
先判斷是否有環，沒環傳回null，有則令慢指針從頭
開始，快指針每次也走一步，當快慢指針相等時，便
找到了入環的第一個節點；
           

圖解

代碼

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast=head,slow=head;
        //判斷是否有環
        while (fast!=null &&fast.next!=null){
            fast= fast.next.next;
            slow= slow.next;
            if(slow==fast){
                break;
            }
        }

       //循環不滿足   表示沒有環;
        if(fast==null || fast.next==null){
            return null;
        }
            slow=head;//慢指針從頭開始
            while(slow!=fast){
                slow=slow.next;
                fast=fast.next;

            }
            return slow;
    }
}
           

若您不會判斷是否有環，可以參考如下連結：

判斷連結清單是否有環