Merge two sorted Linked Lists

1.9K

You are given 2 sorted linked lists with a head pointer. Find a way to merge these 2 lists and return a single sorted list. Try to solve the problem without using any extra space.

Example 1:
List 1: 1 -> 2 -> 4
List 2: 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4

Problem statement

To read about Linked Lists, refer to the post “What is a Linked List“? For our current problem statement, we are given two list heads or we refer to them as two linked lists. These lists are sorted. We need to merge them and return a single sorted linked list.

Brute Force Method:

A naive way to solve the problem would be to put all the elements in one single array and then sort the array. Once the array is sorted we can create a new linked list from the elements and return the result. But this method is neither space efficient, not time efficient. We occupy O(n) extra space and take O(n \log n) time to sort.

Optimized Method:

In the brute force method just discussed above, we never leverage the fact that both the lists are already sorted. This means that we just have to insert the elements of one list somewhere in between the second list. So from a high level perspective, we just need to scan both the lists only once, and by the time we reach the last element we should have a merged sorted list. This is how the algorithm would look like

Algorithm:

1. Initialize two pointers to the start of both the lists.
2. Initialize a sentinel node with a Integer.MIN_VALUE as a dummy node. This value serves as a place holder to start our merged list. We would discard this later.
3. Compare the values at both the pointers of the 2 lists and pick the smaller one.
4. Append this smaller value to the next of sentinel node and move the pointer one step forward from the list that we got the number.
5. Again compare both the values at the two pointers and keep appending the numbers to the list.
6. Stop when we reach the end of one of the list. This would mean that all the elements of this list are finished and the rest of the elements in the second list are greater. So just append all the remaining elements to the sorted list.
7. Return the pointer next to the sentinel node that we defined in step 2.

Code:

public class ListNode {
  public int val;
  public ListNode next;

  public ListNode(int x) {
    val = x;
  }
  
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    // Create a sentinal/dummy node to start
    ListNode returnNode = new ListNode(Integer.MIN_VALUE);

    // Create a copy of this node to iterate while solving the problem
    ListNode headNode = returnNode;

    // Traverse till one of the list reaches the end
    while (l1 != null && l2 != null) {

      // Compare the 2 values of lists
      if (l1.val <= l2.val) {
        returnNode.next = l1;
        l1 = l1.next;
      } else {
        returnNode.next = l2;
        l2 = l2.next;
      }
      returnNode = returnNode.next;
    }

    // Append the remaining list
    if (l1 == null) {
      returnNode.next = l2;
    } else if (l2 == null) {
      returnNode.next = l1;
    }

    // return the next node to sentinal node
    return headNode.next;
  }
}
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)

A working solution is available here.
The code is also available on Github.
A similar problem is found on Leetcode.

Video Explanation: