A SortedDictionary Solution (200ms) & A Plain Merging Solution (650ms)


  • 0
    L

    [1] SortedDictionary Solution (200ms) Time O(N), Space O(N) N is total node-amount

    public ListNode MergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(int.MinValue), cursor = head;
        SortedDictionary<int, ListNode> sd = new SortedDictionary<int, ListNode>();
        for (int i = 0; i < lists.Length; i++)
            while(lists[i] != null)
                if(!sd.ContainsKey(lists[i].val)){
                    sd.Add(lists[i].val, lists[i]);
                    while(lists[i].next != null && lists[i].next.val == lists[i].val)
                        lists[i] = lists[i].next;
                    lists[i] = lists[i].next;
                }else{
                    ListNode tmpSD = sd[lists[i].val].next;
                    sd[lists[i].val].next = lists[i];
                    ListNode tmp = lists[i];
                    while(tmp.next != null && tmp.val == tmp.next.val)
                        tmp = tmp.next;
                    lists[i] = tmp.next;
                    tmp.next = tmpSD;
                }
        foreach(var node in sd){
            cursor.next = node.Value;
            cursor = cursor.next;
            while(cursor.next != null && cursor.next.val == cursor.val)
                cursor = cursor.next;
        }
        return head.next;
    }
    

    [2] Looping the List to merge all nodes Solution (650ms) Time O(N) Space O(1) N is total node-amount

    public ListNode MergeKLists1(ListNode[] lists) {
        ListNode newHead = new ListNode(int.MinValue), newCursor = newHead;
        SortedDictionary<int, List<int>> sd = new SortedDictionary<int, List<int>>();
        int index = -1, min = int.MaxValue;
        for (int i = 0; i < lists.Length; i++)
            if (lists[i] != null && lists[i].val < min){
                min = lists[i].val;
                index = i;
            }
        while (index != -1){
            newCursor.next = lists[index];
            newCursor = newCursor.next;
            while(newCursor.next != null && newCursor.val == newCursor.next.val)
                newCursor = newCursor.next;
            lists[index] = newCursor.next;
            index = -1;
            min = int.MaxValue;
            for (int i = 0; i < lists.Length; i++)
                if (lists[i] != null && lists[i].val < min){
                    min = lists[i].val;
                    index = i;
                }
        }
        return newHead.next;
    }
    

    [3] SortedSet solution

    public ListNode MergeKLists(ListNode[] lists) {
        SortedSet<ListNode> ss = new SortedSet<ListNode>(Comparer<ListNode>.Create((a, b) => a.val == b.val ? a.GetHashCode() - b.GetHashCode() : a.val - b.val));
        ListNode head = new ListNode(int.MinValue), p = head;
        for(int i = 0; i < lists.Length; i++)
            if(lists[i] != null) ss.Add(lists[i]);
        while(ss.Count != 0){
            ListNode nextMerge = ss.Min;
            p.next = nextMerge;
            p = p.next;
            ss.Remove(ss.Min);
            if((nextMerge = nextMerge.next) != null) ss.Add(nextMerge);
        }
        return head.next;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.