Merge k sorted linked lists and return it as one sorted list. The definition of the
ListNode
class and the signature of theMergeKLists
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;
using System.Threading.Tasks;
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))
listSet.Add(new ListNodeWithId(list));
ListNode mergedListHead = 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)
listSet.Add(new ListNodeWithId(nextNode));
var mergedListNode = new ListNode(minVal);
if (mergedListCurrent != null)
{
mergedListCurrent.next = mergedListNode;
mergedListCurrent = mergedListCurrent.next;
}
else
{
mergedListHead = mergedListNode;
mergedListCurrent = mergedListNode;
}
}
return mergedListHead;
}
}
}
Count()
method. This method iterates entire collection every time thewhile
condition is checked. Instead useCount
property of theSortedSet
class orAny()
method. AlthoughCount()
will useCount
property if the collection implementsICollection<T>
I recommend never use this method for determining if the collection is empty or not. \$\endgroup\$