LeetCode 解題練習：Middle of the Linked List

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/middle-of-the-linked-list/

中文描述

指定一個單向鏈結串列 head，找出此鏈結串列的中間節點。如果有兩個中間節點(串列大小為偶數時)，請顯示第二個。

範例一：

輸入  head = [1, 3, 5, 7, 9]

輸出 [5, 7, 9]

因為 5 是中間節點。

範例二：

輸入  head = [1, 3, 5, 7, 9, 11]

輸出 [7, 9, 11]

因為 5 與 7 是中間節點，選擇第二個 7。

解法一：

用迴圈與掃過串列一次，算出串列大小 size， 之後再用從節點開頭逐一走訪至 size // 2 來找出中間節點。

Python Code

# 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]:

        size = 0

        t = head

        while t != None:

            t = t.next

            size += 1

       

        size = size // 2

        i = 0

        while i < size:

            head = head.next

            i += 1

       

        return head

解法二：

使用指標的方式，在走訪串列時，一個指標 middle 指到中間節點，一個指標 end 指到結尾節點。底下以圖解說明：

Python Code

# 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]:

        middle = head

        end = head

        while end != None and end.next != None:

            middle = middle.next

            end = end.next.next

       

        return middle