数据结构--链表刷题(一)快慢指针（下）

 
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
 
        ListNode fast = head;
        ListNode slow = head;
 
        // 只要有环 则fast和slow一定会相遇
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
 
            if(fast == slow) return true;
        }
 
        return false;
        
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while(head != null) {
            if(!seen.add(head)) {
                return true;
            }
 
            head = head.next;
        }
 
        return false;
        
    }
}

1.哈希表的实现
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        Set<ListNode> seen = new HashSet<>();
 
        while(cur != null) {
            // 如果包含  则证明走到了入口点
            if(seen.contains(cur)) {
                return cur;
            }else {
                seen.add(cur);
            }
 
            cur = cur.next;
        }
 
        return null;
    }
}
 
2.双指针
public class Solution {
    public ListNode detectCycle(ListNode head) {
 
 
        // 先找相遇点
        ListNode fast = head;
        ListNode slow = head;
 
 
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
 
 
            if(fast == slow) break;
        }
 
 
        // 跳出循环有两种condition
        if(fast == null || fast.next == null) return null;
 
 
        // fast = head  两个指针一起走 直到相同
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
 
 
        return slow;
    }
}