題目

若一個鏈表中包含環，如何找出的入口結點？如下圖鏈表中，環的入口節點的節點3。

分析

1. 一快（移兩節點）一慢（移一節點）兩指針判斷鏈表是否存在環。
2. 算出環有幾個節點（上一步的兩指針可知是在環中，讓慢指針停止遍歷，讓快指針改為一節點一節點然后兩指針一動一靜的計算出環有多少個節點）。
3. 重置兩指針指向鏈頭，一指針移動2. 步驟得出n，然后兩指針一起移動。當兩指針相遇，此時它們指向的環的入口結點

放碼

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 {@Testpublic 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})));}@Testpublic void test2() {FindEntryNodeOfLoop fl = new FindEntryNodeOfLoop();		assertNull(fl.meetNode(SinglyLinkedList.intArray2List(new int[] {1, 2, 3, 4, 5, 6})));}}