# LeetCode: Merge k sorted lists C#

https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

using System.Collections.Generic;
using Heap;
using Microsoft.VisualStudio.TestTools.UnitTesting;

{/// <summary>
/// https://leetcode.com/problems/merge-k-sorted-lists/
/// </summary>
[TestClass]
public class MergeKSortedLists
{
[TestMethod]
public void LeetCodeExample()
{
ListNode l1 = new ListNode(1);
l1.next = new ListNode(4);
l1.next.next = new ListNode(5);

ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);

ListNode l3 = new ListNode(2);
l3.next = new ListNode(6);
ListNode[] arr = new ListNode[] { l1, l2, l3 };

ListNode res = MergeKSortedListsTest.MergeKLists(arr);

}
}

public class MergeKSortedListsTest
{
public static ListNode MergeKLists(ListNode[] lists)
{
if (lists == null || lists.Length == 0)
{
return null;
}

MinHeap<ListNode> heap = new MinHeap<ListNode>(new ListNodeComparer());
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
foreach (ListNode node in lists)
{
if (node != null)
{
}
}

while (heap.Count > 0)
{
tail.next = heap.ExtractDominating();
tail = tail.next;
if (tail.next != null)
{
}
}

return dummy.next;
}

public class ListNodeComparer : Comparer<ListNode>
{
public override int Compare(ListNode o1, ListNode o2)
{
if (o1.val < o2.val)
return -1;
else if (o1.val == o2.val)
return 0;
else
return 1;
}
}
}
}


you do not need to review the MinHeap code!

 public abstract class Heap<T> : IEnumerable<T>
{
//capacity of the Queue
private const int InitialCapacity = 0;

private int _capacity = InitialCapacity;

//items in the queue
private T[] _heap = new T[InitialCapacity];

//last item in the queue
private int _tail = 0;

//when growing the queue you multiply by Growfactor
private const int GrowFactor = 2;
// if the min size is 0 you grow the queue size by at least Min grow
private const int MinGrow = 1;

//how to compare the keys
protected Comparer<T> Comparer { get; private set; }

//store how many Items are in the queue
public int Count { get { return _tail; } }

//shows the current capacity of the queue
public int Capacity { get { return _capacity; } }

//this function is used in BubbleUp and in GetDominating
protected abstract bool Dominates(T x, T y);

protected Heap() : this(Comparer<T>.Default)
{
}
protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
{
}
protected Heap(IEnumerable<T> collection) : this(collection, Comparer<T>.Default)
{
}

protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
{
if (collection == null)
{
throw new ArgumentNullException("collection");
}

if (comparer == null)
{
throw new ArgumentNullException("comparer");
}

Comparer = comparer;
foreach (var item in collection)
{
if (Count > Capacity)
{
Grow();
}

_heap[_tail++] = item;
}

for (int i = 0; i < Parent(_tail - 1); i++)
{
BubbleDown(i);
}
}

{
if (Count == Capacity)
{
Grow();
}

_heap[_tail++] = item;
BubbleUp(_tail - 1);
}

//when adding a new item we bubble the item from tail-1 up to its'
//correct position
private void BubbleUp(int i)
{
if (i == 0 || Dominates(_heap[Parent(i)], _heap[i]))
{
return; //correct domination (or root)
}

Swap(i, Parent(i));
BubbleUp(Parent(i));
}

// when adding new items into the queue from the CTOR
// we bubble them down
private void BubbleDown(int i)
{
int dominatingNode = Dominating(i);
if (dominatingNode == i)
{
return;
}
Swap(i,dominatingNode);
BubbleDown(dominatingNode);
}

public T GetMin()
{
if (Count == 0)
{
throw new InvalidOperationException("Heap is empty");
}
return _heap[0];
}

private void Swap(int i, int j)
{
T tmp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = tmp;
}

public static int Parent(int i)
{
return (i + 1) / 2 - 1;
}

private void Grow()
{
int newCapcity = _capacity * GrowFactor + MinGrow;
var newHeap = new T[newCapcity];
Array.Copy(_heap, newHeap, _capacity);
_heap = newHeap;
_capacity = newCapcity;
}

//return from 0 up to Count
public IEnumerator<T> GetEnumerator()
{
return _heap.Take(Count).GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}

//when we bubble down, when building the queue from a list in the CTOR
// we need to understand who is dominating i, and we swap them,
// and call bubbleDown again
private int Dominating(int i)
{
int dominatingNode = i;
dominatingNode = GetDominating(YoungChild(i), dominatingNode);
dominatingNode = GetDominating(OldChild(i), dominatingNode);
return dominatingNode;
}

private int GetDominating(int newNode, int dominatingNode)
{
if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
{
return newNode;
}
else
{
return dominatingNode;
}
}

private static int YoungChild(int i)
{
return 2 * (i + 1) - 1;
}

private static int OldChild(int i)
{
return YoungChild(i) + 1;
}

public T ExtractDominating()
{
if (Count == 0) throw new InvalidOperationException("Heap is empty");
T ret = _heap[0];
_tail--;
Swap(_tail, 0);
BubbleDown(0);
return ret;
}

}

public class MinHeap<T> : Heap<T>
{
public MinHeap()
: this(Comparer<T>.Default)
{
}

public MinHeap(Comparer<T> comparer)
: base(comparer)
{
}

public MinHeap(IEnumerable<T> collection) : base(collection)
{
}

public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
: base(collection, comparer)
{
}

protected override bool Dominates(T x, T y)
{
return Comparer.Compare(x, y) <= 0;
}
}


One thing I don't like is, that you merge "in place" - that is: the input linked lists change as a side effect. I would expect them to be untouched by the method. Consider to make a new linked list as the result.

As a micro optimization you could probably spare a couple of ticks, if the input lists contain a lot of duplicate values, by iterate to the first node with a greater value in the second loop:

  while (heap.Count > 0)
{
ListNode node = heap.ExtractDominating();
tail.next = node;

while (node.next != null && node.val == node.next.val)
{
node = node.next;
}

if (node.next != null)
{