CtrlAltDileep

How to Merge Two Sorted Lists in Java

Written by

Dileep

in

Merging two sorted lists is both a programming technique and a LeetCode problem! It’s a part of the blind 75 and is a foundational problem to understand since it sets us up for understanding important algorithms like merge-sort down the line.

If you would prefer a video version of this explanation you can check it out at my youtube channel!

The Problem

According to the LeetCode website:

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]

Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []

Output: []

Example 3:

Input: list1 = [], list2 = [0]

Output: [0]

Solution

The algorithm itself is straightforward.Since we know that the provided linked lists are already sorted we can go through the elements in each list sequentially, compare them to each other, and progressively build the output as we read both. More specifically the algorithm would look like this:

  1. While we have data to read in both list1 and list2:
    1. Compare the current value we are on at list1 to the current value we are on at list2
      1. If the current value of list1 is less than that of list2
        1.  add the current value list1 to the output list
        2.  Mark the current value of list1 as read and get ready to read the next.
      2. Otherwise
        1.  add the current value of list2 to the output list
        2.  Mark the current value of list2 as read and get ready to read the next.
  2. If we still have data in list1 but not in list2 then append all the remaining data in list1 to the output.
  3. otherwise append all the remaining data in list2 to the output since we know that list2 is not empty.

The logic seems straightforward but there are actually two different implementations for it: an iterative and a recursive approach. We will walk through both in this post. Let’s start with the iterative implementation since it is easier to understand.

Iterative implementation

The iterative approach maps to our pseudocode above quite nicely.

public ListNode mergeTwoListsIterative(ListNode list1, ListNode list2) {
   // we initialize the output with a dummy node to make adding to it easier
   ListNode output = new ListNode();
   ListNode outputPointer = output;


   // go through the nodes of each list and compare them to each other
   while(list1 != null && list2 != null) {
       if (list1.val < list2.val) {
           outputPointer.next = list1;
           list1 = list1.next;
       } else {
           outputPointer.next = list2;
           list2 = list2.next;
       }
       outputPointer = outputPointer.next;
   }


   // flush the remaining data of whichever list is not empty to the output
   outputPointer.next = (list1 != null) ? list1 : list2;


   // send output but without the dummy node
   return output.next;
}

Recursive implementation

The recursive implementation is the same idea but the main paradigm shift is that instead of tracking where we are using pointers we rely on the function’s call stack to keep track of the ordering for us. This results in less code but it can be harder to read if you are not comfortable with the concept of recursion. 

If you look at our code below it is very much like our pseudocode but in reverse. We address our base cases if either of the lists are empty and otherwise compare and sort the nodes one by one.

public ListNode mergeTwoListsRecursive(ListNode list1, ListNode list2) {
   if (list1 == null) {
       return list2;
   }


   if (list2 == null) {
       return list1;
   }


   if (list1.val < list2.val) {
       list1.next = mergeTwoListsRecursive(list1.next, list2);
       return list1;
   } else {
       list2.next = mergeTwoListsRecursive(list1, list2.next);
       return list2;
   }
}

Time and Space Complexity

The time complexity is actually the same regardless of whether you implement this in the recursive or the iterative manner. Since we have to go through all the elements of each list once the time complexity is O(m + n). The space complexity is O(1) for the iterative solution. We only create pointers once in our code and reuse them for the rest of the program. The recursive solution has space complexity of O(m + n) because we can build up a call stack the size of both lists combined.

Key Takeaways

Hopefully this post was enlightening. We explored two ways to merge two sorted linked lists. We also walked through the space and time complexities of each solution. Although this is a simple problem it is foundational for understanding more complex algorithms like merge sort which are used in more advanced LeetCode problems. 

More posts