題目出處
難度
easy
個人範例程式碼 - two pointers
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return None
slow = head
fast = slow.next
while(fast is not None and fast.next is not None):
slow = slow.next
fast = fast.next.next
else:
if(fast is None): # odd case
return slow
else: # fast is not None, fast.next is None: # even case
return slow.next
算法說明
同向的快慢 pointers，這題目雖然簡單，但很考慮細節的處理。
- 這部分可以看下圖，說明請見 Boundary conditions ：
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為 None 的情況，輸出 None。
Boundary conditions
我們依照上面的圖片繼續說明：
基本上拆成兩種狀況討論：
- odd case：奇數情況，特性為 fast 直接指到 None 上，return slow
- even case：偶數情況，特性為 fast.next 才指到 None 上 (或 fast 有值卻進入了 else part)，return slow.next
結束條件
fast or fast.next is None 的時候，我們再來分析情況
- (至少要自己本身能指到 None)