溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
golang中怎么利用leetcode實現(xiàn)一個環(huán)形鏈表，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。
給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。 如果鏈表無環(huán)，則返回 null。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環(huán)。
說明：不允許修改給定的鏈表。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：tail connects to node index 1
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：tail connects to node index 0
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。
示例 3：
輸入：head = [1], pos = -1
輸出：no cycle
解釋：鏈表中沒有環(huán)。
解題思路：
1，首先用快慢指針判斷是否有環(huán)
2，假設(shè)快慢指針相遇的位置為環(huán)起點m后第p個位置，環(huán)剩余q個位置
則：
A，m＋p=2*(m+p)-k*(p+q) k為整數(shù)，跟m長度與環(huán)大小比有關(guān)
B，假設(shè)k＝1 則，m＝q
C，m＝k*(p+q)-p=(k-1)*(p+q)+q
3，由此可知，如果慢指針從相遇位置開始，新指針從頭開始，則相遇位置一定為環(huán)起點
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func detectCycle(head *ListNode) *ListNode { fast:=head slow:=head flag:=false for fast!=nil && fast.Next!=nil{ fast=fast.Next.Next slow=slow.Next if fast!=nil && slow==fast{ flag=true break } } if !flag{ return nil } fast=head for fast!=slow{ fast=fast.Next slow=slow.Next } return fast}
看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼