FilesExpand file tree

 master

/

EntryNodeInListLoop.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (44 loc) · 1.17 KB

 master

/

EntryNodeInListLoop.java

Top

File metadata and controls

• Code
• Blame

51 lines (44 loc) · 1.17 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package _23;

import structure.ListNode;

public class EntryNodeInListLoop {

public static ListNode<Integer> meetingNode(ListNode<Integer> head) {

ListNode<Integer> slow = head;

ListNode<Integer> fast = head;

boolean hasCycle = false;

while (fast != null && fast.next != null) {

slow = slow.next;

fast = fast.next.next;

if (slow == fast) {

hasCycle = true;

break;

}

}

if (!hasCycle) {

return null;

}

slow = head;

while (slow != fast) {

slow = slow.next;

fast = fast.next;

}

return slow;

}

public static void main(String[] args) {

// 1->2->3->4->5->6

// |________|

ListNode<Integer> head = new ListNode<>(1);

head.next= new ListNode<>(2);

ListNode<Integer> node = new ListNode<>(3);

head.next.next = node;

node.next = new ListNode<>(4);

node.next.next = new ListNode<>(5);

node.next.next.next = new ListNode<>(6);

node.next.next.next.next = node;

ListNode<Integer> meet = meetingNode(head);

if(meet==null) {

System.out.println("没有环");

} else {

System.out.println("环的入口值:" + meet.val);

}

}

}