溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
golang中怎么利用leetcode實現一個環形鏈表，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細講解，有這方面需求的人可以來學習下，希望你能有所收獲。
給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 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
解釋：鏈表中沒有環。
解題思路：
1，首先用快慢指針判斷是否有環
2，假設快慢指針相遇的位置為環起點m后第p個位置，環剩余q個位置
則：
A，m＋p=2*(m+p)-k*(p+q) k為整數，跟m長度與環大小比有關
B，假設k＝1 則，m＝q
C，m＝k*(p+q)-p=(k-1)*(p+q)+q
3，由此可知，如果慢指針從相遇位置開始，新指針從頭開始，則相遇位置一定為環起點
/** * 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}
看完上述內容是否對您有幫助呢？如果還想對相關知識有進一步的了解或閱讀更多相關文章，請關注億速云行業資訊頻道，感謝您對億速云的支持。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
