您好,登錄后才能下訂單哦!
這篇文章主要介紹“c++環(huán)形鏈表怎么實現(xiàn)”的相關(guān)知識,小編通過實際案例向大家展示操作過程,操作方法簡單快捷,實用性強,希望這篇“c++環(huán)形鏈表怎么實現(xiàn)”文章能幫助大家解決問題。
算法:
該類題目的核心點在于如何判斷是環(huán)形鏈表,核心思想是:兩個人在環(huán)上跑步,跑的快的早晚會追上跑的慢的。
是快慢指針的典型使用場景。
題目1: 環(huán)形鏈表
代碼實現(xiàn):
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */func hasCycle(head *ListNode) bool { if head == nil || head.Next == nil { return false } slow := head // 慢指針一次走一步 fast := head.Next // 快指針一次走兩步 for slow != fast { if slow == nil || fast == nil { return false } slow = slow.Next fast = fast.Next if fast != nil { fast = fast.Next } } return true}
題目2:環(huán)路檢測
代碼實現(xiàn):
// 算法:該題目主要分兩步,第一步是找到環(huán)形鏈表中的相交的位置。
// 第二步是讓慢指針指向鏈表首部,快指針位置不變,
// 然后快慢指針每次都走一步,再次相遇就是環(huán)形鏈表的入口位置。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
s, f := head,head
for f != nil && f.Next != nil {
s = s.Next
f = f.Next.Next
if f == s { // 判斷是不是有環(huán)
break
}
}
if f == nil || f.Next == nil {
// 此時的快指針在環(huán)里面,理論上這兩個都不應(yīng)該為空;
// 只有一個節(jié)點的話,f.Next == nil
return nil
}
s = head
for s != f {
s = s.Next
f = f.Next
}
return s
}
關(guān)于“c++環(huán)形鏈表怎么實現(xiàn)”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識,可以關(guān)注億速云行業(yè)資訊頻道,小編每天都會為大家更新不同的知識點。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。