Solution: Merge Two Sorted Lists

Statement#

Given the heads of two sorted linked lists, list1 and list2, merge these lists into a single sorted list. This involves integrating all the nodes from both lists while ensuring that their sorted order is preserved. Return the head of the merged linked list as the output.

Constraints:

• $0$ $\leq$ Number of nodes in both lists $\leq 50$

• $-100 \leq$ Node.data $\leq 100$

• Both lists are sorted in a non-decreasing order.

Solution#

The objective is to combine the given linked lists into a single, sorted linked list while maintaining their inherent order. This can be accomplished through a systematic approach where we traverse both lists simultaneously and compare the values of the current nodes in both lists. The smaller value is chosen, and the respective node becomes part of the merged list. This process continues iteratively, and eventually, the merged list contains all the nodes of list1 and list2 in a non-decreasing order. We can then return this list as the correct output.

To store the output, a new linked list is created with its first node, dummy, initialized to $-1$. This node will serve as the starting point of the merged list. A pointer, prev, is initialized to point to the dummy node. This will be used to keep track of the last node in the merged list. Next, a loop is started, which continues as long as both head1 and head2 are not None. In each iteration:

• A comparison is made between the data of the current nodes pointed to by head1 and head2.

  • If the value pointed to by head1 is less than or equal to the value pointed to by head2, it means the next node in the merged list should come from head1. Therefore, prev.next is set to head1 and then head1 moves to the next node in its list.

  • Otherwise, the next node in the merged list should come from head2. Therefore, prev.next is set to head2, and head2 moves to the next node in its list.

• Regardless of which node has been added to the merged list, prev is updated to point to this recently added node.

The loop ends if either head1 or head2 becomes None. Now, once we are outside the loop, if there are any remaining nodes in either list1 or list2, we append all of them to the merged list at once.

• If head1 is not None, it means there are nodes remaining in list1, so the rest of list1 is directly appended to the merged list using prev.next $=$ head1.

• Otherwise, there are nodes remaining in list2, so the rest of list2 is appended to the merged list using prev.next $=$ head2.

By this time, we will have all the nodes present in list1 and list2 integrated into the new linked list in a non-decreasing order. We'll return the node next to the dummy node of this merged list, i.e., dummy.next.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s look at the code for the solution below:

Time complexity#

The while loop iterates as long as both list1 and list2 have nodes left to be merged. In the worst case, it will run for the total number of nodes in both lists, which is $n + m$ and will take $O(n+m)$ time, where $n$ is the number of nodes in list1 and $m$ is the number of nodes in list2. The operations inside the loop and outside the loop take constant time. Therefore, the overall time complexity of this solution is $O(n + m)$.

Space complexity#

The space complexity of this solution is $O(1)$, since it uses only a constant amount of extra space.