Close

# Mohit Athwani

MA There are so many ways to solve this problem. Let’s look at some of them:

1. Iterate through all the nodes in all the “`k“` lists and dump the values in an array, then sort the array, iterate through the sorted array, generate the linked list and return the head. This obviously doesn’t sound like an efficient algorithm.
2. We can use a Min Heap with max size “`k“`. We insert the heads of the linked lists into the heap and as we remove from the heap, we should insert the next element from the list that had it’s element evicted from the heap. Using a heap will give us a time complexity of “`O(lg k)“` for removing and inserting. But, there are “`N“` removals and insertions therefore the time complexity will be “`O(N lg k)“`
3. We can solve this in linear time by merging 2 lists at a time.

We are going to take the third approach discussed above. Let’s consider that we have 5 linked lists represented by `A, B, C, D, E`. Let the `•` notation represent the merger of two lists.

The initial array is:

 A B C D E

In our first iteration, we will remove the lists `A` and `B`, merge them and put them back in the array. At this point our array will look like:

 C D E A•B

In the second iteration, we will remove the lists `C` and `D`, merge them and put them back in the array. At this point our array will look like:

 E A•B C•D

In the third iteration, we will remove the lists `E` and `A•B`, merge them and put them back in the array. At this point our array will look like:

 C•D A•B•E

In the fourth iteration, we will remove the lists C•D and A•B•E, merge them and put them back in the array. At this point our array will look like:

 A•B•E•C•D

At this point, we have merged all `k` lists in `k-1` iterations. Basically we keep iterating until the array containing the heads of the `k` linked lists has only one element. At this point we are guaranteed that this is the merged list.

This problem is listed as hard on Leetcode and at first it doesn’t seem so. While the actual algorithm to implement this is actually pretty easy, there are several conditions that one needs to take care of.

Let’s look at them one by one.

1. What do you do if the array containing the heads of the lists is empty?
```guard lists.count > 0 else {
return nil
}
```
2. What if the the size of the array containing the heads has only one element?
```guard lists.count >= 2 else {
return lists.first!
}```
3. When we pull the first 2 elements out of the array, there are chances one of them, or both of them will be“` nil“`. If the first one is “`nil“`, just remove it from the array and “`continue“` the loop. If the second is “`nil“`, remove it from the list and put the first one back in the list so that it is considered for a merge in a future operation and “`continue“` the loop.
```while tempLists.count > 1 {
guard let l1 = tempLists else {
tempLists.removeFirst()
continue
}

tempLists.removeFirst()
guard let l2 = tempLists else {
tempLists.removeFirst()
tempLists.append(l1)
continue
}

tempLists.removeFirst()
tempLists.append(merge(l1: l1, l2: l2))
}```
4. When merging two arrays, what if the 2 heads are pointing to the same instance?
```if l1 === l2 {
return l1
}```
5. When merging two arrays, you have to account for one list being shorter than the other. So before returning, we must take the longer list and append it’s elements to the result list.
```if list1 == nil {
while list2 != nil {
tail?.next = list2
tail = tail?.next
list2 = list2?.next
}
}

if list2 == nil {
while list1 != nil {
tail?.next = list1
tail = tail?.next
list1 = list1?.next
}
}```

A guaranteed solution is only possible iff the above conditions are satisfied.

Time Complexity: Merging two lists take `O(n)` time where `n` is the total number of elements in the 2 lists. In our case we are merging two lists `k-1` times which gives us a total time complexity of `O(kN)` where `N` is the number of all elements

Space Complexity: I am creating a temporary array to hold the heads which will be `O(k)` space.

Solution available on Github.