C# LeetCode 23. Merge k Sorted Lists (二)

緣起:

    我上篇文章寫完後，有拿給志璿老大看，他看完後，就問了我問題

    所以我就開始思考，要怎麼讓程式快點

    我這時才意識到，原來這題就是做到一半的 Merge Sort，所以就打算用 Merge Sort 來重寫程式

想法:

    一樣拿 [[1,3,4],[2,6],[1,4,5]] 來當例子，首先，要額外再開記憶體空間，長度是 (原本array長度)/2，如除 2 不能整除的話，要再加一

圖一

    new array[0] 會是 array[0] 跟 array[1] merge 的結果，由於沒有 array[3] 可以跟 array[2] 合併，所以 new array[1] 就直接是 array[2]

圖二

    我們現在單獨看 new array，它會是長這樣

    當 array 的長度等於 2 的時候，其實就是在做兩個 List 的合併，直接呼叫合併兩個 List 的 method，把 new array[0] 跟 new array[1] 傳入即可。

程式碼:

public class Solution
{
    public ListNode MergeKLists(ListNode[] arrayListNode)
    {
        if (arrayListNode == null) return null;
        arrayListNode = arrayListNode.Where(o => !(o == null)).ToArray();
        if (arrayListNode.Length == 0) return null;
        if (arrayListNode.Length == 1) return arrayListNode[0];
        if(arrayListNode.Length == 2) return _Merge2ListNode(arrayListNode[0], arrayListNode[1]);

        ListNode[] newArrayListNode = _NewArray(arrayListNode);
        while (newArrayListNode.Length != 2) newArrayListNode = _NewArray(newArrayListNode);

        return _Merge2ListNode(newArrayListNode[0], newArrayListNode[1]);
    }

    private ListNode[] _NewArray(ListNode[] arrayListNode)
    {
        ListNode[] newArrayListNode = new ListNode[arrayListNode.Length/2 + arrayListNode.Length % 2];
        int iArrayListNodeTailIndex = arrayListNode.Length - 1;

        for(int i = 0; i < newArrayListNode.Length; i++)
        {
            int iIndex1 = i * 2;
            int iIndex2 = i * 2 + 1;

            if (iIndex2 > iArrayListNodeTailIndex) newArrayListNode[i] = arrayListNode[iIndex1];
            else newArrayListNode[i] = _Merge2ListNode(arrayListNode[iIndex1], arrayListNode[iIndex2]);
        }

        return newArrayListNode;
    }
     
    private ListNode _Merge2ListNode(ListNode listNode1, ListNode listNode2)
    {
        if (listNode1 == null && listNode2 == null) return null;
        if (listNode1 == null) return listNode2;
        if (listNode2 == null) return listNode1;

        ListNode listNodeHead = null;
        ListNode listNodeTrave = null;

        if(listNode1.val <= listNode2.val)
        {
            listNodeHead = listNode1;
            listNode1 = listNode1.next;
        }
        else
        {
            listNodeHead = listNode2;
            listNode2 = listNode2.next;
        }
        listNodeTrave = listNodeHead;

        while(listNode1 != null && listNode2 != null)
        {
            if (listNode1.val <= listNode2.val)
            {
                listNodeTrave.next = listNode1;
                listNode1 = listNode1.next;
            }
            else
            {
                listNodeTrave.next = listNode2;
                listNode2 = listNode2.next;
            }
            listNodeTrave = listNodeTrave.next;
        }

        if (listNode1 == null) listNodeTrave.next = listNode2;
        else listNodeTrave.next = listNode1;

        return listNodeHead;
    }
}

    34~74行 : 這是合併兩個 ListNode 的方法，這邊就不再贅述它的原理。

    

    5~9行 : 跟上次的程式碼差不多，多了一行判斷長度為 2 的，直接回傳 [0] 跟 [1] 合併的結果。

    17~32行 : 本篇的主角，開新的陣列來記錄兩兩 ListNode 的合併，最後回傳新陣列。

    19行 : 新 array 的大小會是原本 array 長度的 1/2，如果沒辦法被 2 整除就把商再加 1。

    20行 : iArrayListNodeTailIndex 是紀錄原本 array 末端的 index，避免後面在做兩兩合併時超出原先陣列的範圍。

    22~29行 : 兩兩 ListNode 合併，要檢查 iIndex2 是否有超出原先陣列的範圍，像是圖二的 new array[1] 原本應該會是 array[2] 跟 array[3] 的合併，但原本的 array 只到 2，所以就直接把 array[2] 給 new array[1] (27行)。

    11~14行 : 反覆開新陣列來記錄兩兩 ListNode 的合併，一直到新開的陣列大小為 2 為止，最後回傳 [0] 跟 [1] 的合併就會是答案了。

結果:

    

    執行的時間整個大越進，而且記憶體的使用也沒多出多少。