How to Merge Two Sorted Lists into One

Learn to merge two sorted linked lists into one linked list with most efficiency using Java and improve your DSA skills.

We are given two sorted linked lists, list1 and list2, and we need to merge them into one sorted list and return the head of this list.

We will solve this problem using two approaches — first is two-pointer and second is recursion, and see time and space complexities in both of them.

Two-Pointer Approach

In this approach, we will use dummy and current, two objects of ListNode, a while loop and solve this problem. Here is a Java method that does it using this approach.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while(list1!=null && list2!=null){
        if(list1.val<list2.val){
            current.next = list1;
            list1 = list1.next;
        }else{
            current.next = list2;
            list2 = list2.next;
        }
        current = current.next;
    }
    if(list1!=null) current.next = list1;
    else current.next = list2;
    return dummy.next;
}

In this code, we are using dummy to keep reference of the head of the sorted list to return in the end, and current for tracking the node where the next sorted node is to be added.

It runs the while loop until one of the given lists becomes null, compares the two lists, adds the smaller list's node to current, moves that list to the next node, and updates current with current.next.

After the loop, we add the remaining nodes of whichever list is not null to current and return the head of the sorted list from dummy.next. The time and space complexities of this approach are O(m+n) and O(1).

Recursion Approach

In this approach, we will call the same given method recursively by passing the next node of the smaller node and the other node. Below is the code for solving this problem using this approach.

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

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

In this code, when any of the given lists becomes null, it acts as the recursion stopper. We are returning the list that is not null from the stopper condition because the other list still has remaining nodes.

Then we simply compare the heads of both lists. Whichever node has the smaller value becomes the head of the merged list, and we recursively merge the rest of the nodes. This solution is a little more simple in terms of readability.

The time complexity of this solution is O(m+n), and space complexity is also O(m+n) due to the call stack. Both solutions are time-efficient, but the two-pointer approach is more memory-efficient.

I hope you enjoyed solving this problem with me, understood both of the solutions, and found this post useful for improving your DSA skills.

Thanks for reading! 🤝 Happy Coding! ✨