Leetcode — 328. Odd Even Linked List (中文)

問題連結: https://leetcode.com/problems/odd-even-linked-list/

給予一個單向鏈結陣列singly linked list, 把所有奇數位置的節點串在一起, 後面再接偶數位置的節點們
並試著用O(1)的空間複雜度及O(節點數)的時間複雜度來解這題

範例: 
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

想法:

如果你很害怕解這類問題, 其實不需要緊張, 這題你只要把你需要做的事情畫下來, 真的沒有想像中的那麼難

因為題目已要求我們用O(1)空間來解這題, 我這邊就不解釋我們如何用O(n)來解了 (邏輯大概就是我們用兩個佇列來存奇數位置的節點 和偶數位置的節點, 然後我們再慢慢地一個一個把他們連在一起)

若我們只想用O(1)空間, 我們需要同時控制奇數位置的節點 和偶數位置的節點, 一次幫助兩個都指到正確的下一個節點
我們將用兩個變數oddNode 和 evenNode 來控制我們現在要"幫忙指向正確道路" 的奇數位置節點及偶數位置節點

程式邏輯:

我們其實在迴圈中的每次節點走訪時, 只做兩件事

1. oddNode 改成指向 原本下個節點 的下一個節點
2. evenNode 改成指向 原本下個節點 的下一個節點

每次幫oddNode跟evenNode指向正確的節點後, 我們將會繼續同樣的動作直到oddNode或evenNode的下個節點已是空值

👷舉例來說, 假設原本的 head = [1, 2, 3, 4, 5, 6, 7]

🔧Step 0. 各變數的初始位置
現在狀態: oddNode — 1️⃣; evenNode — 2️⃣

step 0 result

🔧Step 1. 讓各節點指向正確的節點 —
oddNode: 1️⃣ 改指向 3️⃣
evenNode: 2️⃣ 改指向 4️⃣

step 1 — assign next nodes process

指完後, 我們將oddNode 跟evenNode往下個節點走 我們才能做一樣的動作在下個節點上
現在狀態: oddNode — 3️⃣; evenNode — 4️⃣

step 1 result

🔧Step 2. 讓各節點指向正確的節點 —
oddNode: 3️⃣ 改指向 5️⃣
evenNode: 4️⃣ 改指向 6️⃣

step 2 — assign next nodes process

指完後, 我們將oddNode 跟evenNode往下個節點走 我們才能做一樣的動作在下個節點上
現在狀態: oddNode — 5️⃣; evenNode — 6️⃣

step 2 result

🔧Step 3. 讓各節點指向正確的節點 —
oddNode: 5️⃣ 改指向 7️⃣
evenNode: 6️⃣ 改指向 null (已到結尾)

step 3 — assign next nodes process

指完後, 我們將oddNode 跟evenNode往下個節點走 我們才能做一樣的動作在下個節點上
現在狀態: oddNode — 7️⃣; evenNode — null

step 3 result

👷我們最後一步就是把odd list跟 even list連在一起 — 也就是連結odd list的最後一個節點(也就是現在oddNode的位置) 跟 even list的第一個節點

final list

public ListNode oddEvenList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode evenHead = head.next;
        ListNode evenNode = evenHead;
        ListNode oddNode = head;
        while(oddNode.next!=null && evenNode.next!=null)
        {
            oddNode.next = oddNode.next.next; 
            oddNode = oddNode.next;
            evenNode.next = evenNode.next.next;
            evenNode = evenNode.next;
        }
        oddNode.next = evenHead;
        return head;
    }

時間複雜度: O(n); 空間複雜度: O(1)