一個鏈表中包含環，請找出該鏈表的環的入口結點

代碼：

package offer;
class Node3
{
?? ?int val;
?? ?Node3 next = null;
?? ?Node3(int val)
?? ?{
?? ??? ?this.val = val;
?? ?}
}
public class ti23 {
?? ?public static Node3 FindInterNode(Node3 head)
?? ?{
?? ??? ?if(head==null||head.next==null)
?? ??? ?{
?? ??? ??? ?return null;
?? ??? ?}
?? ??? ?Node3 fast = head;//快指針每次走兩步
?? ? ? ?Node3 slow = head;//每次走一步
?? ? ? ? ? while(fast!=null && fast.next !=null)//因為fast每次要走兩步，所有需要判斷fast的下一個是否為空
?? ? ? ? ? {
?? ? ? ??? ? ? slow = slow.next;
?? ? ? ??? ? ? fast = fast.next.next;
?? ? ? ??? ? ? //判斷是否相遇 相遇后讓快指針從頭開始走，每次都是走一步，第二次相遇的節點就是環的入口
?? ? ? ??? ? ? if(fast.val == slow.val)
?? ? ? ??? ? ? {
?? ? ? ??? ??? ? ?fast = head;
?? ? ? ??? ??? ? ?while(fast.val != slow.val)
?? ? ? ??? ??? ? ?{
?? ? ? ??? ??? ??? ? ?fast = fast.next;
?? ? ? ??? ??? ??? ? ?slow = slow.next;
?? ? ? ??? ??? ? ?}
?? ? ? ??? ? ? }
?? ? ? ??? ? ? if(fast.val == slow.val)
?? ? ? ??? ? ? {
?? ? ? ??? ??? ? ? return slow;
?? ? ? ??? ? ? }
?? ? ? ? ? }
?? ? ? ? ? return null;//要是沒有相遇，此鏈表沒有環返回空
?? ?}
?? ?public static void main(String[] args)
?? ?{
?? ??? ?Node3 node1 = new Node3(1);
?? ??? ?Node3 node2 = new Node3(2);
?? ??? ?Node3 node3 = new Node3(3);
?? ??? ?Node3 node4 = new Node3(4);
?? ??? ?Node3 node5 = new Node3(5);
?? ??? ?Node3 node6 = new Node3(6);
?? ??? ?node1.next = node2;
?? ??? ?node2.next = node3;
?? ??? ?node3.next = node4;
?? ??? ?node4.next = node5;
?? ??? ?node5.next = node6;
?? ??? ?Node3 head = node1;
?? ??? ?node6.next = node3;
?? ??? ?System.out.println(FindInterNode(head).val);
?? ?}
}
?

總結

以上是生活随笔為你收集整理的【剑指offer】面试题23：链表中环的入口节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。