題目出處
難度
medium
個人範例程式碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
slow = fast = head
while(fast and fast.next):
slow = slow.next
fast = fast.next.next
if fast == slow: # find loop
break # out of while-else, no else
else:
return None
while (head != slow):
head = head.next
slow = slow.next
return head
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
首先我們先找出是否有 loop，找到後我們在開始找迴圈的起點。
證明
- 假設迴圈的長度為 l
- 起點到迴圈入口的距離為 a
- slow, fast 相遇處為 a+b (相距迴圈入口 b)
fast 走的距離，
= 可以是 a+l(走了一圈迴圈)+b
= 也等於 2*(a+b) = 兩倍的 slow 移動距離
這樣我們可以推得 a+l+b = 2*(a+b), 得到 l = a+b
- 我們現在想要求 a
a = l-b，注意圖上 l-b，也就是把相遇處剩下的路再繼續走完。
因此我們只要
- 從 head 走 a
- 從相遇處走 l-b
走到下一個相遇處就是我們要的 a。
input handling
如果沒有 head 或沒有 head.next，return None
Boundary conditions
透過 while(fast and fast.next) 控制搜尋範圍
python while-else 用法說明
一般來說，我們通常都只會使用到 while，
但其實在 python 中，while 是可以搭配 else 使用的。
邏輯如下：
while(條件成立):
# 成立時循環
else: # 當不成立時，出現在這
# 當條件不成立時，開始作這邊的事情
這個寫法，可能很多人覺得好像有沒有 else 似乎不會有太大的影響?
畢竟當 while 條件不成立後，後續的程式碼「本來就會執行」
沒有錯!!!! 但是這個小細節，卻可以讓我們的程式碼邏輯更漂亮!
例如說當我們有無關 while 的相關內容，我們才應該擺在外面，
但有時候是剛結束迴圈時有一些收尾的相關內容要處理，這時候用 else 的寫法就相當漂亮了!
範例
假設我們要把一個 mylist 「純手動」印成 [1,2,3] 的樣子，
最後還要印出一個 finish!
mylist = [1,2,3]
idx = 0
print('[', end = '')
while(idx < len(mylist)):
print(mylist[idx], ',')
idx += 1
else:
print(']')
print('finish!')
這個例子應該就很好懂了，我們集中「把要處理 list 列印的動作」放在 while-else 裡面，
最後比較無關的 finish! 放在 while-else 外面，
這樣看起來程式碼邏輯有沒有比都放在外面更清楚了呢? (當然，見仁見智啦XDDD，我覺得有XD)
特殊用法 - while-else 搭配 break 使用的情況
這也是我近期解題才發現的，當 while - else 搭配 break 使用時，能發揮更好閱讀的效果!
請讀者先想像一下，下面的程式碼會印出什麼呢?
while(True):
break
else:
print(1)
print(2)
答案不是 1 2 !!! 而是只有 2 !!!
這樣我們就能夠更進階的使用這個功能了，
- 「透過 while 迴圈條件結束的，寫在 else 裡面」
- 「如果是透過 break 結束的，寫在最外面」