LeetCode如何找出鏈表中環(huán)的入口節(jié)點

這篇文章主要介紹LeetCode如何找出鏈表中環(huán)的入口節(jié)點，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

題目

若一個鏈表中包含環(huán)，如何找出的入口結(jié)點？如下圖鏈表中，環(huán)的入口節(jié)點的節(jié)點3。

分析

1. 一快（移兩節(jié)點）一慢（移一節(jié)點）兩指針判斷鏈表是否存在環(huán)。

2. 算出環(huán)有幾個節(jié)點（上一步的兩指針可知是在環(huán)中，讓慢指針停止遍歷，讓快指針改為一節(jié)點一節(jié)點然后兩指針一動一靜的計算出環(huán)有多少個節(jié)點）。

3. 重置兩指針指向鏈頭，一指針移動2. 步驟得出n，然后兩指針一起移動。當兩指針相遇，此時它們指向的環(huán)的入口結(jié)點

放碼

import com.lun.util.SinglyLinkedList.ListNode;

public class FindEntryNodeOfLoop {

	public ListNode find(ListNode head) {
		
		//1.判斷是否存在環(huán)
		ListNode meetNode = meetNode(head);
		
		if(meetNode == null) {
			return null;
		}
		
		int nodesInLoop = 1;
		
		ListNode node1 = meetNode;
		
		//2.計算環(huán)內(nèi)節(jié)點
		while(node1.next != meetNode) {
			nodesInLoop++;
			node1 = node1.next;
		}
		
		//3.先移動node1, 次數(shù)為環(huán)中節(jié)點的數(shù)目
		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) {//鏈表只有一個節(jié)點
			return null;
		}
			
		ListNode fast = slow.next;
		
		while(fast != null && slow != null) {//可能循環(huán)幾次才能碰上
		
			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為入口節(jié)點
		
		assertEquals(3, fl.find(n1).val);
		
		//沒有環(huán)的鏈表
		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})));
	}
	
}

以上是“LeetCode如何找出鏈表中環(huán)的入口節(jié)點”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道！