55. 链表中环的入口结点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null
思路：https://blog.nowcoder.net/n/76e8af2d2fad49f990cde6e6b60a4d79?f=comment
快慢指针，快指针一次走两步，慢指针一次走一步，相遇后，快指针回到头结点，以一次一步的速度和慢指针一起走，再次相遇的结点即是环的入口点
1 public class Solution { 2 3 public ListNode EntryNodeOfLoop(ListNode pHead) 4 { 5 6 if(pHead == null || pHead.next == null || pHead.next.next == null) 7 return null; 8 ListNode fast = pHead.next.next, low = pHead.next; 9 while(fast != low){ 10 if(fast.next == null || low == null) 11 return null; 12 fast = fast.next.next; 13 low = low.next; 14 } 15 fast = pHead; 16 while(fast != low){ 17 fast = fast.next; 18 low = low.next; 19 } 20 return fast; 21 } 22 }
思路：把所有结点存入一个 ArrayList 中，第一个重复的结点就是入口结点，如果没有重复结点，则无环
1 import java.util.ArrayList; 2 public class Solution { 3 4 public ListNode EntryNodeOfLoop(ListNode pHead) 5 { 6 // 如果链表只有一个结点或者没有结点则直接返回空 7 if(pHead == null) 8 return null; 9 ArrayList<ListNode> list = new ArrayList<ListNode>(); 10 list.add(pHead); 11 ListNode p = pHead.next; 12 while(p != null){ 13 if(list.contains(p)){ 14 return p; 15 } 16 list.add(p); 17 p = p.next; 18 19 } 20 return null; 21 } 22 }
原文：https://www.cnblogs.com/hi3254014978/p/12416446.html