目錄
LeetCode-142題
LeetCode-142題
給定一個鏈表的頭節點head，返回鏈表開始入環的第一個節點，如果鏈表無環，則返回null
class Solution {public ListNode detectCycle(ListNode head) {// checkif (head == null || head.next == null)return null;// 鏈表是否有環的標識，初始值設置為falseboolean hasCycle = false;// 定義兩個指針，一個快指針[fast]，一個慢指針[slow]，并且它們開始都指向頭節點ListNode fast = head;ListNode slow = head;// fast指針一次前進兩個節點，slow指針一次前進一個節點while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;// 如果fast和slow能相遇，鏈表存在環if (fast == slow) {hasCycle = true;break;}}// 鏈表無環，返回nullif (!hasCycle) {return null;}// fast指針回到初始位置，也就是頭節點// 快慢指針都每次前進1個節點，再次相遇的位置就是第一次開始入環的節點位置fast = head;for (; ; ) {// 有可能在回到頭節點就相遇if (slow == fast)return slow;slow = slow.next;fast = fast.next;if (slow == fast)return slow;}}private static class ListNode {int val;ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}}
}
)
