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

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

``````public ListNode MergeKLists(ListNode[] lists) {
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)){
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;
}
}
``````

[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) {
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;
}
}
}
``````

[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));
for(int i = 0; i < lists.Length; i++)