876.鏈表的中間節點

• 給你單鏈表的頭結點 head ，請你找出并返回鏈表的中間結點。如果有兩個中間結點，則返回第二個中間結點。
• 思路：快慢指針，創建兩個指針fast和slow，fast指針每次移動兩步，slow指針每次移動一步，這樣當fast指針指向列表以外的值的時候（退出循環的時候），slow指針正好指向鏈表的中間節點。

- # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def middleNode(self, head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""if not head or not head.next:# 若鏈表不存在或只有一個節點時,返回headreturn headfast, slow = head, headwhile fast and fast.next:fast = fast.next.nextslow = slow.nextreturn slow

• 時間復雜度：O(n)
• 空間復雜度:：O(1)
• 快慢指針的優勢
  • 解決鏈表中常見的問題：例如找中點、判斷環、回文鏈表等，常常用到快慢指針。
  • 高效的空間利用：只使用常數空間，避免了使用額外的空間（如棧或哈希表等）。