iT邦幫忙

2024 iThome 鐵人賽

DAY 2
0
佛心分享-刷題不只是刷題

Leecode刷題系列 第 25

D26:Q142Linked List Cycle II

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20241013/201693092FRZJrMG7y.png
這題要找到單向鏈結串列中的循環節點,如果沒循環就回傳 null,這類型問題需要了解兩點:判斷有沒有循環、找到循環的起點。
分析:
鏈結串列的問題通常用快慢指針法解決,這個方法既有效率又不會用額外的空間,這題可以用兩個指針,一個慢指針(每次走一步)和一個快指針(每次走兩步)如果快指針和慢指針相遇,就表示鏈結串列存在循環。

步驟:
確認有沒有循環,讓快慢指針從鏈結串列的頭開始,慢指針每次移動一步,快指針每次移動兩步,如果相遇,說明有循環存在,不然快指針到 null(鏈結結束),說明沒循環。
找到循環的起點,當快慢指針相遇,把其中一個指針移回鏈結串列的頭,另一個指針保持在相遇點,兩個指針再以同速度(每次走一步)前進,直到它們再次遇到,相遇的節點就是循環的起點。

程式碼:
#Definition for singly-linked list.
#class ListNode(object):
#def init(self, x):
#self.val = x
#self.next = None

class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None

    #初始化快慢指針
    slow, fast = head, head
    
    #判斷有沒有循環
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # 找到循環起點
            slow = head
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow
    
    return None

心得:
這題通過快慢指針法,解決判斷鏈結串列中是否有循環及找到循環的起點的問題,這種方法的空間複雜度是 O(1),是高效的解法,學這題的過程,讓我理解雙指針的運用,重點是在鏈結串列中找循環或特定節點,這類問題常出現在面試,了解背後的解題技巧對解決其他類似的問題也蠻有用的。


上一篇
D25:Q132Palindrome Partitioning II
下一篇
D27:Q146LRU Cache
系列文
Leecode刷題28
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言