java中環形鏈表的示例分析

這篇文章主要為大家展示了java中環形鏈表的示例分析，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶大家一起來研究并學習一下“java中環形鏈表的示例分析”這篇文章吧。

給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環。

說明：不允許修改給定的鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環。

鏈表結構

1class ListNode {
2    int val;
3    ListNode next;
4
5    ListNode(int x) {
6        val = x;
7        next = null;
8    }
9}

答案：

 1public ListNode detectCycle(ListNode head) {
 2    if (head == null || head.next == null || head.next.next == null)
 3        return null;
 4    ListNode slow = head.next;
 5    ListNode fast = head.next.next;
 6    while (slow != fast) {
 7        if (fast.next == null || fast.next.next == null)
 8            return null;
 9        slow = slow.next;
10        fast = fast.next.next;
11    }
12    slow = head;
13    while (slow != fast) {
14        slow = slow.next;
15        fast = fast.next;
16    }
17    return slow;
18}

解析：

首先通過快慢指針判斷鏈表是否有環，如果沒環則返回null，如果有環肯定會在環中的某一點相遇，在相遇的時候快指針從相遇的那一刻開始，慢指針從頭開始，每次都只走一步，再次相遇的時候就是環的入口。畫個圖來分析一下更有助于理解。

我們假設鏈表有環。快慢指針都從A開始沿著箭頭方向出發，假如快慢指針在B點相遇，那么慢指針走過的路徑是A->C->D->B,如果把鏈表完整走完一次就差B->C這段路徑了。快指針走過的路徑是A->C->D->B->C->D-B,如果把鏈表完整走完兩次就差B->C這段和A->C這段路徑了，所以我們可以得出A->C等于B->C，即C點就是環的入口。

常用的java框架有哪些

1.SpringMVC，Spring Web MVC是一種基于Java的實現了Web MVC設計模式的請求驅動類型的輕量級Web框架。2.Shiro，Apache Shiro是Java的一個安全框架。3.Mybatis，MyBatis 是支持普通 SQL查詢，存儲過程和高級映射的優秀持久層框架。4.Dubbo，Dubbo是一個分布式服務框架。5.Maven，Maven是個項目管理和構建自動化工具。6.RabbitMQ，RabbitMQ是用Erlang實現的一個高并發高可靠AMQP消息隊列服務器。7.Ehcache，EhCache 是一個純Java的進程內緩存框架。

以上就是關于“java中環形鏈表的示例分析”的內容，如果該文章對您有所幫助并覺得寫得不錯，勞請分享給您的好友一起學習新知識，若想了解更多相關知識內容，請多多關注億速云行業資訊頻道。