通过快慢指针寻找环链表入口（java）_快慢指针找环入口

快慢指针可以判断出链表是否为环链表(不同于循环链表)，网上此类文章比较多，可以查阅相关实现，同时快慢指针也能找出环链表的入口。
上图是一个环链表，当快慢指针（快指针步长没有限制，慢指针为1）相遇时，我们可以判断到列表中有环，这时重新设定一个新指针指向链表的起点，且步长与慢指针一样为1，则慢指针与“新指针”相遇的地方就是环的入口，证明这一结论涉及数论知识，感兴趣的可以查阅相关资料。

public class FastSlowTest {
    public static void main(String[] args) {
        Node<String> first = new Node<String>("aa", null);
        Node<String> second = new Node<String>("bb", null);
        Node<String> third = new Node<String>("cc", null);
        Node<String> fouth = new Node<String>("dd", null);
        Node<String> fifth = new Node<String>("ee", null);
        Node<String> sixth = new Node<String>("ff", null);
        Node<String> seventh = new Node<String>("gg", null);

        first.next = second;
        second.next = third;
        third.next = fouth;
        fouth.next = fifth;
        fifth.next = sixth;
        sixth.next = seventh;
        seventh.next=third;

        String entrance=getEntrance(first);
        System.out.println(entrance);
    }

    public static String getEntrance(Node<String> first){
        if(!isCircle(first)){
            return null;
        }else {
            Node<String> slow = first;
            Node<String> fast = first;
            Node<String> temp = null;
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow.equals(fast)) {
                    temp=first;
                    continue;
                }
                if(temp!=null){
                	temp=temp.next;
                	if(temp.equals(slow))
                		break;
                }
            }
            return temp.item;
        }
    }

    public static boolean isCircle(Node<String> first){
        Node<String> slow=first;
        Node<String> fast=first;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow.equals(fast))
                return true;
        }
        return false;
    }
    
	private static class Node<T> {
        T item;//数据
        Node next;//指向下一个结点
        public Node(T t, Node next) {
            this.item = t;
            this.next = next;
        }
    }
}
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
60
61
62
63
64
65
66
67