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

緣起:

    前陣子有在看 jserv 的 "你所不知道的 C 語言: linked list 和非連續記憶體"，看到他拿 LeetCode 的題目來當 pointer to pointer 的實作範例，我看著看著，就想說要來寫看看題目。

    merge 兩個 list 比較簡單，所以就跳過。由於工作上是使用 C# 來開發，所以我解題也就用 C# 來寫了。

    要解的題目在這邊。

想法:

    這是題目提供的 ListNode Class

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

    

    那個 MergeKLists 的方法會傳入 ListNode class 的陣列，然後我們最後要回傳組起來的 List 的頭。

    想法蠻直觀的，第一步是先把 ListNode 由小到大做排序，然後每次都取第一個陣列的 ListNode 的頭，串到我們要回傳的 List 裡。每次從 List 取走一個 Node 後，要檢查陣列最前面那個 List 是否已經碰到了 null，是的話，移動紀錄陣列頭位置的 index，把它往後挪。如果取完 ListNode 後，陣列頭不是 null 的話，會需要重新做排序，因為陣列頭的 ListNode 可能不會是最小值。

    我這邊隨便用一組測試資料 [[1,3,4],[2,6],[1,4,5]] 來圖解，紅圈框起來的是 ListNode 陣列

圖一

    先對陣列做排序 (依每個 ListNode 頭的 val)，我使用的是插入排序法

圖二

    我有用兩個變數來記錄陣列頭跟陣列尾。開始串回傳的 ListNode，把陣列頭的第一個 ListNode 抓出來

圖三

    這時需要重新排一下陣列

圖四

    排完後

圖五

    繼續取陣列頭 ListNode 出來串

圖六

    然後再排序....，就這樣做下去。我們快轉幾個步驟，跳到這邊

圖七

    這時再把陣列頭的 ListNode 取走後，它會剩下 NULL。

圖八

    我們就把 arrayHead 往前挪，這樣就可以避開 NULL 的處理

圖九

    再繼續重複上述的步驟，做到 arrayHead 跟 arrayTail 一樣為止

圖十

    這時就可以直接把 ListNodeHead 的最後跟陣列最後的 ListNode 串起來，回傳 ListNodeHead，結束。

圖十一

程式碼:

    我是開一個 C# 的 Console 專案來測試程式碼的，在 Main 裡面測，這邊就只貼 Solution Class 的程式碼

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];

        _InsertionSort(arrayListNode);

        ListNode listNodeHead = null;
        ListNode listNodeTrave = null;
        int iArrayHeadIndex = 0;
        int iArrayTailIndex = arrayListNode.Length - 1;

        while(iArrayHeadIndex != iArrayTailIndex)
        {
            if(listNodeHead == null)
            {
                listNodeHead = _Pop(ref arrayListNode[iArrayHeadIndex]);
                listNodeTrave = listNodeHead;
            }
            else
            {
                listNodeTrave.next = _Pop(ref arrayListNode[iArrayHeadIndex]);
                listNodeTrave = listNodeTrave.next;
            }

            if (arrayListNode[iArrayHeadIndex] == null)
            {
                iArrayHeadIndex++;
            }
            else
            {
                int iExchangeIndex = iArrayHeadIndex;
                while(iExchangeIndex+1 <= iArrayTailIndex && arrayListNode[iExchangeIndex].val > arrayListNode[iExchangeIndex + 1].val)
                {
                    _Swap(ref arrayListNode[iExchangeIndex], ref arrayListNode[iExchangeIndex + 1]);
                    iExchangeIndex++;
                }
            }
        }

        listNodeTrave.next = arrayListNode[iArrayTailIndex];

        return listNodeHead;
    }

    private void _InsertionSort(ListNode[] arrayListNode)
    {
        for(int i = 1; i < arrayListNode.Length; i++)
        {
            int iExchangeIndex = i;
            while (iExchangeIndex -1 >=0 && arrayListNode[iExchangeIndex-1].val > arrayListNode[iExchangeIndex].val)
            {
                _Swap(ref arrayListNode[iExchangeIndex-1], ref arrayListNode[iExchangeIndex]);
                iExchangeIndex--;
            }
        }
    }

    private ListNode _Pop(ref ListNode listNode)
    {
        ListNode tmp = listNode;
        listNode = listNode.next;
        return tmp;
    }

    private void _Swap(ref ListNode node1, ref ListNode node2)
    {
        ListNode tmp = node1;
        node1 = node2;
        node2 = tmp;
    }
}

    70~75 行 : 交換兩個 ListNode，要用 ref 關鍵字才能更改到原本物件。

    63~68 行 : 取出 ListNode 的第一個 Node，然後把 ListNode 的頭指向下一個 Node。

    50~61 行 : 對傳進來的 array 做插入排序 (對應圖一~圖二)。

    5~8 行 : 檢查輸入的 arrayListNode，先做 null 檢查，再來是去除陣列中的 null 值之後，再查看 array 的長度，0 的話一樣回傳 null，1 的話就直接回傳陣列第一個 ListNode。我們的程式邏輯是在 array 長度 >=2 時才適用的。

    12、13 行 : 紀錄要回傳的 ListNode 的頭，另一個是用來記錄 ListNode 的尾，方便串接新的 Node。

    17行 :  我們的邏輯是一直做到 iArrayHeadIndex 跟 iArrayTailIndex 碰頭為止。

    19~28 行 : 串接要回傳的 ListNode，有分 listNodeHead 還沒初始化跟初始化完之後的串接方式。 

    30~32行 : 在取走陣列頭的一個 Node 後檢查陣列頭是否為 NULL，是的話，把 iArrayHeadIndex 往後移 (對應圖八~圖九)。

    34~42行 : 如果取完 Node 後，陣列頭不是 NULL，就重新排序 (對應圖四)。

    45 行 : 串接陣列最後一個 ListNode (對應圖十一)。

結果:

    這是 submit 後的評分

    速度很慢，但記憶體使用量還行。