# Merge K Sorted List

Posted on

Problem

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

}
}
}

Solution

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
{