題目描述

對于一個給定的鏈表，返回環的入口節點，如果沒有環，返回null。

?

步驟：?
<1> 定義兩個指針p1和p2，在初始化時都指向鏈表的頭節點。?
<2> 如果鏈表中的環有n個節點，指針p1先在鏈表上向前移動n步。?
<3> 然后指針p1和p2以相同的速度在鏈表上向前移動直到它們相遇。?
<4> 它們相遇的節點就是環的入口節點。?
? ? 那么如何得到環中的節點數目？即通過一快一慢兩個指針來解決這個問題。當兩個指針相遇時，表明鏈表中存在環。兩個指針相遇的節點一定是在環中。可以從這個節點出發，一邊繼續向前移動一邊計數，當再次回到這個節點時，即可得到環中的節點數了。

public class TestIsCircleList {public static void main(String[] args) {TestIsCircleList t = new TestIsCircleList();ListNode a = new ListNode(1);ListNode b = new ListNode(2);ListNode c = new ListNode(3);ListNode d = new ListNode(4);ListNode e = new ListNode(5);ListNode f = new ListNode(6);ListNode g = new ListNode(7);a.next = b;b.next = c;c.next = d;d.next = e;e.next = f;f.next = g;g.next = d; // 形成環狀//boolean isHave = t.hasCycle(a);//System.out.println(isHave);detectCycle(a);}public static ListNode detectCycle(ListNode head) {ListNode slow = head; // 慢指針ListNode fast = head; // 快指針boolean isHaveCirle = false;while(null != fast && null != fast.next){slow = slow.next;fast = fast.next.next;if(slow == fast){// 通過一快一慢兩個指針來解決這個問題。當兩個指針相遇時，表明鏈表中存在環System.out.println("鏈表有環");isHaveCirle = true;break;}}if(!isHaveCirle){return null;}int circleCount = 1;slow = slow.next;// 求環的節點數while(fast != slow){circleCount++;// 一繼續向前移動一邊計數，當再次回到這個節點時，即可得到環中的節點數了slow = slow.next;}ListNode pre = head;ListNode post = head;for(int i=0;i<circleCount;i++){post = post.next;}while(pre != post){pre = pre.next;post = post.next;}return pre;} }

?

?

?

?

?

總結

以上是生活随笔為你收集整理的常考数据结构和算法:链表中环的入口节点的全部內容，希望文章能夠幫你解決所遇到的問題。

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