LeetCode 筆記 - 876. Middle of the Linked List

Posted on 標籤
尋找鏈結串列的中間節點。本文運用經典的快慢指針（Two Pointers）大法，透過快指針每次移動兩步、慢指針移動一步的速差，讓慢指針在遍歷結束時精確停在中間位置，是一篇展示指針技巧如何優化遍歷效能的範例。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 876. Middle of the Linked List

image 11

給一個 Linked list，請回傳中間的 node

解題思維

這題使用了 Two Pointers (超好用一定要學會

因為是需要找到中間的 node，所以 head 每移動兩步 result 移動一步就可以了
結束之後 result 就會停在中間的 node

完成 🥰

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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]:
        
        result = head
        
        index = 0
        while head:
            head = head.next
            index += 1
            
            if index % 2 == 0:
                result = result.next
            
        return result

也許你也會想看看