142. 环形链表 II - 力扣（Leetcode）

这个逻辑过程还是很有趣的，有点数学在里面。

不过是初中水平。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//环形链表II142
public class LinkedListCycleII142 {
	public static void main(String[] args){
		ListNode head = initLinkedList(new int[]{1,2,3,4});
		ListNode res = new Solution().detectCycle(head);
		System.out.println(res == null ? "null" : res.val);
	}

	//做环的init
	public static ListNode initLinkedList(int[] nums){
    	ListNode head = new ListNode(nums[0]);
    	ListNode cur = head,node;
    	for(int i = 1; i < nums.length; i++){
    		node = new ListNode(nums[i]);
    		cur.next = node;
    		cur = node;
    	}
    	//下面这里设置成不成环
    	//cur.next = head.next;
    	return head;
    }

}

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;
	} 
}

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) {
        		//有环
        		
        		slow = head;
        		while(slow != fast){
        			slow = slow.next;
        			fast = fast.next;
        		}
        		return slow;
        	}
        }
        return null;
    }
}