題目連結: 328. Odd Even Linked List

題目描述:給定一個單向鏈結串列的頭節點 head，請將所有索引為奇數的節點排在索引為偶數的節點前面，並保持它們在各自組內的相對順序不變。

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Python

解題思路:
我們的目標是將Linked List「解開」成兩條，一條只包含奇數位置節點，另一條只包含偶數位置節點——然後再把它們頭尾相連，這題就結束了。不過要注意題目的要求 保持它們在各自組內的相對順序不變。

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return head
        slow = head
        fast = head.next
        fast_head = fast
        while fast and fast.next:
            slow.next = fast.next
            slow = fast.next
            fast.next = slow.next
            fast = slow.next
        slow.next = fast_head
        return head

演算法分析:

• 初始兩個指針一個指向head,一個指向head下一個，另一個則是指向fast的頭後續連接兩個Linked List會需要。
• 進入迴圈，首先將當前的奇數節點跳過中間的偶數節點，直接連接到下一個奇數節點。
• 更新當前slow值(奇數)。
• 將當前的偶數節點跳過中間新的奇數節點，直接連接到下一個偶數節點。
• 更新當前fast值(偶數)。
• 迴圈結束後，將slow最後點連結至fast的頭。

複雜度分析:

• 時間複雜度為 O(n)。

  1. 我們只需要遍歷一次Linked List即可完成重排。

• 空間複雜度： O(1)。

下回開始介紹樹!
有問題可以底下留言!
下回見!!