【链表 环形链表 】双指针_环形链表 双指针

博客

环形链表

快指针走两步，慢指针走一步，如果有环，最终会在环中相遇。
快指针回到表头，慢指针停在相遇点，之后都走一步，最终会在环入口相遇。
leetcode141

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)
            return true;
        }
        return false;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

leetcode142

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(true){
            if(fast == null || fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                break;
            }
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

链表中间结点 快慢指针

leetcode876