Merge Sorted Linked Lists

One of LeetCode’s easy problems involves merging two sorted linked list. Given two input lists the result should be a sorted combination of the lists.

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

The approach to this problem involves iterating over both lists and comparing the value of the elements. Then adding the smaller value to our return list. Let’s get into it. However, we also need to think about a few cases along the way.

We could start by comparing the first two elements in the both lists and set that as our initial return list node. However, we could have a case when both or one of the list is empty resulting in an error. The solution to this case is to check if either list is empty as we iterate over the list.

while (l1 != null && l2 !=null)

During the iteration we compare the current values in the list and the smaller value is appended to our return list. If the values are equivalent we can append any of the values, since in the next iteration the other value will also be appended to the list.

In order to move through our linked list nodes, without an index or counter we simply can simply move the position of the head node. This removes the current node and maintains the other nodes.

We need to build a return linked list that contains the sorted values. We could do this by appending the smaller element to the end of our return list. The caveat to this is we don’t know the tail of our new list. This means we will not maintain state of the next values, instead we will end up overwriting the next element, this is not what we want.

To solve this problem we need to keep track of our start node and tail node. This allows us to retrieve all elements at the end of the iterations by going back to the start. We can also update the list by updating the tail node. To handle the case of empty list we set our initial head node to some value. It is common to set this dummy node as -1. Initially our tail is at the head thus we set this value as well.

ListNode dummy = new ListNode(-1);
ListNode tail = dummy;

On each iteration we will move the tail and thus change the path of the return list and maintain a chain of elements. Let’s have a look at a couple of iterations.

Initial state

Dummy: -1
Tail: -1

First iteration

Dummy: -1 -> 2 -> 4
Tail: 1 -> 2 -> 4

Second Iteration

Dummy: -1 -> 1 -> 3 -> 4
Tail: 1 -> 3 -> 4

By moving only the tail we can maintain the list. We do this until the two lists (L1 and L2) are at the end.

One final case, in the event the linked list are of different sizes. We need to add all the remaining nodes in the longer list to the tail of our list. Since the linked lists are already sorted we can add it without any need for sorting.

if (l1 != null) tail.next = l1;
if (l2 != null) tail.next = l2;

Finally, we return the next value of our dummy linked list. This removes the initial dummy node (-1) from our return list.

Happy coding!