java中環(huán)形鏈表的示例分析

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

給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回 null。

為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。如果 pos 是 -1，則在該鏈表中沒(méi)有環(huán)。

說(shuō)明：不允許修改給定的鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋?zhuān)烘湵碇杏幸粋€(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

示例 2：

輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋?zhuān)烘湵碇杏幸粋€(gè)環(huán)，其尾部連接到第一個(gè)節(jié)點(diǎn)。

示例 3：

輸入：head = [1], pos = -1
輸出：no cycle
解釋?zhuān)烘湵碇袥](méi)有環(huán)。

鏈表結(jié)構(gòu)

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}

解析：

首先通過(guò)快慢指針判斷鏈表是否有環(huán)，如果沒(méi)環(huán)則返回null，如果有環(huán)肯定會(huì)在環(huán)中的某一點(diǎn)相遇，在相遇的時(shí)候快指針從相遇的那一刻開(kāi)始，慢指針從頭開(kāi)始，每次都只走一步，再次相遇的時(shí)候就是環(huán)的入口。畫(huà)個(gè)圖來(lái)分析一下更有助于理解。

我們假設(shè)鏈表有環(huán)?？炻羔樁紡腁開(kāi)始沿著箭頭方向出發(fā)，假如快慢指針在B點(diǎn)相遇，那么慢指針走過(guò)的路徑是A->C->D->B,如果把鏈表完整走完一次就差B->C這段路徑了?？熘羔樧哌^(guò)的路徑是A->C->D->B->C->D-B,如果把鏈表完整走完兩次就差B->C這段和A->C這段路徑了，所以我們可以得出A->C等于B->C，即C點(diǎn)就是環(huán)的入口。

常用的java框架有哪些

1.SpringMVC，Spring Web MVC是一種基于Java的實(shí)現(xiàn)了Web MVC設(shè)計(jì)模式的請(qǐng)求驅(qū)動(dòng)類(lèi)型的輕量級(jí)Web框架。2.Shiro，Apache Shiro是Java的一個(gè)安全框架。3.Mybatis，MyBatis 是支持普通 SQL查詢(xún)，存儲(chǔ)過(guò)程和高級(jí)映射的優(yōu)秀持久層框架。4.Dubbo，Dubbo是一個(gè)分布式服務(wù)框架。5.Maven，Maven是個(gè)項(xiàng)目管理和構(gòu)建自動(dòng)化工具。6.RabbitMQ，RabbitMQ是用Erlang實(shí)現(xiàn)的一個(gè)高并發(fā)高可靠AMQP消息隊(duì)列服務(wù)器。7.Ehcache，EhCache 是一個(gè)純Java的進(jìn)程內(nèi)緩存框架。

以上就是關(guān)于“java中環(huán)形鏈表的示例分析”的內(nèi)容，如果該文章對(duì)您有所幫助并覺(jué)得寫(xiě)得不錯(cuò)，勞請(qǐng)分享給您的好友一起學(xué)習(xí)新知識(shí)，若想了解更多相關(guān)知識(shí)內(nèi)容，請(qǐng)多多關(guān)注億速云行業(yè)資訊頻道。