Data Structures & Algorithms in Java – Linked List – Merge Two Sorted Lists

Problem :

Given two sorted lists merge them without copying them to a new linked list.

For example:

Given the linked lists: [1,3,4] and [1,2,4].

merge them into [1,1,2,3,4]

Try out the solution here:

https://leetcode.com/problems/merge-two-sorted-lists/submissions/

Solution:

Hint:

• Use recursion or iterative solution , comparing the smallest of the head nodes at each step and adjusting pointers pointing to their heads.

Explanation:

The problem has a recursive solution and an iterative solution.

Let’s look at both of them.

In the recursive solution,

We divide the bigger “merge” problem to smaller sub “merge” problems.

We initially create a head node which will represent the head node of the merged lists.

We see which one of the two linked lists has the smallest head node and then assign the head node to it.

Once we do that we have processed one node and so increment the pointer pointing to the head to the next node.

Now we are left with two lists again , we merge these lists recursively and append the result to the tail of the head node we created.

Once we reach the end of either of the lists , we need to append the rest of the other list to the result calculated so far.

ALGORITHM:

STEP 1: If any of the lists is null return the other list – this is the base condition

STEP 2: Create a head node

STEP 3: Find the smallest of the head nodes of the given lists and point head node to it

STEP 3a: Increment the smallest node pointer to the next node

STEP 3b: Point the next node of the head to the merged list of the remaining nodes (found recursively)

STEP 4: Return the head node.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        
        if(list1 == null) return list2;
        
        
        if(list2 == null) return list1;
        
        
     ListNode head = null;
        
           if(list1.val < list2.val){
               
               
               head = list1;
               
               list1 = list1.next ;
               head.next = mergeTwoLists(list1,list2);
               
           }else{
               
               
               head = list2;
               
               list2 = list2.next;
               
               head.next = mergeTwoLists(list1,list2);
           }
        
        
        return head;
    }
}

Time complexity of the above algorithm is O(m + n ) where m and n represent the number of nodes in each linked list.

Space complexity is also O(m + n ) as we make m + n recursive calls in the worst case and each need a stack memory.

In iterative solution ,

We create two nodes , a head node and a tail node.

Both point to an empty node initially.

Imagine two pointers pointing to them.

Also point two pointers to the given linked lists (we can use the list reference themselves as pointers – list1 and list2)

We will be appending nodes one by one to the empty node pointed to by the head and the tail node initially.

First we compare the head of the two given nodes , take the smallest and append it to the next node of the tail node.

We don’t bother the head node as we need it to return it at the end(output is the head node of the merged lists).

We increment the pointer to the node just processed.

Also we increment the tail node to point to the end of the tail so that we can keep appending nodes to it.

When one of the linked list ends , we take the remaining of the other linked list and append it to the tail again.

Finally we return the next node of the head which is currently pointing to the head of the merged list.

We dont return the head as such as it is pointing to an empty node.

Iterative solution:

ALGORITHM:

STEP1: Create two pointers, head and tail and point them to an empty node.

STEP2: While both the linked list pointers are not null do the following

STEP 2b: Find the smallest of the two nodes and assign it to the next node of the tail

STEP 2c: Increment the pointer to the smallest node to the next node

STEP 2d: Increment the tail so that new nodes can be appended to it.

STEP 3: If any of the list is null , merge the rest of the remaining list to the next node of the tail.

STEP 4: Return next node of the head which now points to the head of the merged lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

      
        
        ListNode head = new ListNode();
        
        ListNode tail = head;;
        
        
        while(list1 != null && list2 != null){
        if(list1.val < list2.val){
            
            tail.next = list1;
            
            list1 = list1.next;
        }else{
            
            tail.next = list2;
            
            list2 = list2.next;
        }
            
            tail = tail.next;
            
        }
        
        
        if(list1 == null){
            
            tail.next = list2;
        }else if(list2 == null){
            
            tail.next = list1;
        }
        return head.next;
    }
}

Time complexity is O(m + n ) since we need to iterate through all the nodes in the worst case.

Space complexity is O(1) since we dont need any space in proportion to the input. We create head and tail pointers which are just two nodes irrespective of the sizes of the given linked lists.

That’s it!