LeetCode如何找出链表中环的入口节点

import com.lun.util.SinglyLinkedList.ListNode;

public class FindEntryNodeOfLoop {

	public ListNode find(ListNode head) {
		
		//1.判断是否存在环
		ListNode meetNode = meetNode(head);
		
		if(meetNode == null) {
			return null;
		}
		
		int nodesInLoop = 1;
		
		ListNode node1 = meetNode;
		
		//2.计算环内节点
		while(node1.next != meetNode) {
			nodesInLoop++;
			node1 = node1.next;
		}
		
		//3.先移动node1, 次数为环中节点的数目
		node1 = head;
		for(int i = 0; i < nodesInLoop; i++)
			node1 = node1.next;
		
		ListNode node2 = head;
		while(node1 != node2) {
			node1 = node1.next;
			node2 = node2.next;
		}
		
		return node1;
	}

	
	public ListNode meetNode(ListNode head) {
		
		if(head == null)
			return null;
		
		ListNode slow = head.next;
		
		if(slow == null) {//链表只有一个节点
			return null;
		}
			
		ListNode fast = slow.next;
		
		while(fast != null && slow != null) {//可能循环几次才能碰上
		
			if(fast == slow) {
				return fast;
			}
			
			slow = slow.next;
			fast = fast.next;
			
			if(fast != null) {
				fast = fast.next;
			}
		}
		
		return null;
	}
	
}

import static org.junit.Assert.*;

import org.junit.Test;

import com.lun.util.SinglyLinkedList;
import com.lun.util.SinglyLinkedList.ListNode;

public class FindEntryNodeOfLoopTest {

	@Test
	public void test() {	
		FindEntryNodeOfLoop fl = new FindEntryNodeOfLoop();
		
		ListNode n1 = new ListNode(1);
		ListNode n2 = new ListNode(2);
		ListNode n3 = new ListNode(3);
		ListNode n4 = new ListNode(4);
		ListNode n5 = new ListNode(5);
		ListNode n6 = new ListNode(6);
		
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		n5.next = n6;
		
		n6.next = n3;//n3为入口节点
		
		assertEquals(3, fl.find(n1).val);
		
		//没有环的链表
		assertNull(fl.find(SinglyLinkedList.intArray2List(new int[] {1, 2, 3, 4, 5, 6})));
		
	}
	
	@Test
	public void test2() {
		FindEntryNodeOfLoop fl = new FindEntryNodeOfLoop();		
		assertNull(fl.meetNode(SinglyLinkedList.intArray2List(new int[] {1, 2, 3, 4, 5, 6})));
	}
	
}