# Merge K Sorted List

Merge k sorted linked lists and return it as one sorted list. The definition of the ListNode class and the signature of the MergeKLists method can't be modified.

Below is my submission to LeetCode which has been accepted and run time is not that bad (better than 55% of the submissions). But I am curious why mine is not in the top 10%. There must be something that can be improved in terms of algorithm performance. Can you please suggest something in this regard?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LeetCode23_MergeKSortedList
{

/// <summary>
/// This class definition is given as input. And can't be modified.
/// </summary>
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}

/// <summary>
/// Just so that we can add an Id field
/// </summary>
public class ListNodeWithId : ListNode
{
public Guid id { get; set; } = Guid.NewGuid();
public ListNodeWithId (ListNode n): base (n.val)
{
next = n.next;
}
}
/// <summary>
/// To be able to handle duplicate valued nodes
/// </summary>
public class DuplicateKeyComparer : IComparer<ListNodeWithId>
{
public int Compare(ListNodeWithId x, ListNodeWithId y)
{
int result = x.val.CompareTo(y.val);

if (result == 0)
return x.id.CompareTo(y.id);   // Handle equal valued node as distinct still
else
return result;
}

}
public class Solution
{
public ListNode MergeKLists(ListNode[] lists)
{
var listSet = new SortedSet<ListNodeWithId>(new DuplicateKeyComparer());
foreach (var list in lists.Where(x => x != null))

ListNode mergedListCurrent = null;

while (listSet.Count() > 0)
{
var min = listSet.First();

int minVal = min.val;
listSet.Remove(min);

var nextNode = min.next;
if ( nextNode != null)

var mergedListNode = new ListNode(minVal);

if (mergedListCurrent != null)
{
mergedListCurrent.next = mergedListNode;
mergedListCurrent = mergedListCurrent.next;
}
else
{
mergedListCurrent = mergedListNode;
}
}

}
}
}

• I write in comments because my note is too small to be an answer. Don't use Count() method. This method iterates entire collection every time the while condition is checked. Instead use Count property of the SortedSet class or Any() method. Although Count() will use Count property if the collection implements ICollection<T> I recommend never use this method for determining if the collection is empty or not. Sep 10, 2017 at 5:04

    return x.id.CompareTo(y.id);   // Handle equal valued node as distinct still


Your tie-breaker is a high-entropy GUID. The contest inputs may have long runs of monotonic non-decreasing or non-increasing values, for which a boring sequential serial number id might do better at preserving runs than a GUID.

Rather than listSet, which is redundant with the declaration, I would prefer a name of simply lists.

I can't say I'm crazy about trivial definitions like this:

            int minVal = min.val;


At this point:

            var mergedListNode = new ListNode(min.val);


you have a perfectly nice min list node, right? But you discard it, and create a duplicate copy of it? Why? Seems like you're just keeping the GC busy.

I wouldn't mind seeing this happen before the while begins:

            else
{
mergedListCurrent = mergedListNode;
}


You asked about speed. I think your algorithm is a perfectly good one - relying on SortedSet makes sense. But you do lots of node copying and reallocation, and you do lots of SortedSet operations. It's all in line with N log N, that's good, I'm just saying its more operations than necessary. Recall that Timsort is fast because it preserves runs. (BTW, it's not clear to me that stability is buying you anything, that keeping an ID on the side is helping you.)

Let's try to be lazy. Consider a 2-way merge, where first list has values of 1 to 1e6 (or they could even all be 1e6), and second list has values of million and one up to 2e6 (or they're all 2e6). Minimum amount of work we could possibly do is linear scan of first list, splice its final node to front of second list, scan to end, and return. No SortedSet operations, no deallocation or new allocations. What would you need to attain high speed in that special case? Either peek at minimum value before adding a node back into the set, or else you'd need some way of obtaining first two values so you can keep looping while you're below that 2nd lowest starting value. Good luck!

• Getting rid of the extra allocation (and reusing min) unfortunately didn't make much improvement in runtime - although I agree it is something that needs to be done regardless. Changing GUID to plain int (incremental) actually improved the runtime quite a bit. Now it is better than 69% of all submissions. I didn't quite follow your last paragraph - but I think I will once I re-read it a few times. Thanks! Sep 10, 2017 at 3:06
• Oh and the ID is really for making duplicate keys possible with the Set. It's not really about stability. If there are other better ways to use SortedSet with duplicate values, I am interested to hear about them. I am reluctant to write my heapsort from scratch. Sep 10, 2017 at 3:08
• Guava's TreeMultiset may be of use. (And a heapsort implementation actually comes out fairly small.) My 2e6 thought experiment was just noting that some common workloads will benefit if you cache a target value, in this case a million and one, and do simple comparisons against the target value without incurring function call overhead. It's still O(1) constant time, just with a smaller constant buried by the notation.
– J_H
Sep 10, 2017 at 16:13
• Are there other ways to use SortedSet with duplicate values? Yes. It's slightly horrible, but you can tack hash-of-node onto the end of the key, to uniqueify it, and strip off that suffix prior to use. Any nonce would do, even a serial number. Bear in mind that using (immutable) strings as keys would run the risk of high interning overhead.
– J_H
Sep 10, 2017 at 16:17