Merge Two Sorted Lists | Leetcode 21 Solution

Introduction

The “Merge Two Sorted Lists” problem (Leetcode 21) is a classic algorithmic challenge that tests your understanding of linked lists and pointers. The goal is to merge two sorted linked lists into a single sorted linked list. In this blog post, we will explore multiple solutions to this problem, ranging from a naive approach to optimized solutions, all implemented in Java. Let’s dive into the problem!

Problem Statement for Merge Two Sorted Lists

You are given the heads of two sorted linked lists, l1 and l2. Merge these two lists into one sorted list, and return the head of the merged list.

The merge process must be done in-place, which means that no extra space should be used for merging.

Different Approaches to solve Merge Two Sorted Lists

Naive Solution: Using ArrayList (Not Optimized) for Merge Two Sorted Lists

The naive approach to merging two sorted linked lists involves using an ArrayList to temporarily store all the elements, sorting them, and then reconstructing the merged linked list. While this solution works, it is not optimized due to the additional time and space complexities introduced by the use of an ArrayList.

Steps:

1. Traverse list1 and list2 and add all their nodes’ values to an ArrayList.
2. Sort the ArrayList to ensure all elements are in ascending order.
3. Create a new linked list using the sorted elements from the ArrayList.

Implementation in Java:

import java.util.ArrayList;
import java.util.Collections;

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // Step 1: Add all values to an ArrayList
    ArrayList<Integer> values = new ArrayList<>();
    
    while (list1 != null) {
        values.add(list1.val);
        list1 = list1.next;
    }
    
    while (list2 != null) {
        values.add(list2.val);
        list2 = list2.next;
    }
    
    // Step 2: Sort the ArrayList
    Collections.sort(values);
    
    // Step 3: Create a new linked list from the sorted values
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;
    
    for (int val : values) {
        current.next = new ListNode(val);
        current = current.next;
    }
    
    return dummy.next;
}

Complexity Analysis

• Time Complexity:
  • O(n+m) to traverse list1 and list2 and store values in an ArrayList.
  • O((n+m)log⁡(n+m)) to sort the ArrayList.
  • O(n+m) to construct the merged linked list.
  • Overall: O((n+m)log⁡(n+m)).
• Space Complexity:
  • O(n+m) for storing the values in an ArrayList.
  • O(n+m) for the new linked list.
  • Overall: O(n+m).

Iterative Approach for Merge Two Sorted Lists

This approach involves traversing both linked lists simultaneously while comparing their current nodes. The smaller node is attached to the merged list, and the pointer in the respective list is advanced.

Steps:

1. Create a dummy node as the starting point of the merged list.
2. Use a pointer to build the merged list by comparing nodes from list1 and list2.
3. If one list is exhausted, attach the remaining nodes of the other list.

Java Code

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(-1);
    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;
    }

    current.next = (list1 != null) ? list1 : list2;

    return dummy.next;
}

Complexity

• Time Complexity: O(n+m)O(n + m)O(n+m), where nnn and mmm are the lengths of list1 and list2.
• Space Complexity: O(1)O(1)O(1), since no extra space is used.

Recursive Approach for Merge Two Sorted Lists

The recursive method divides the problem into smaller sub-problems by comparing the head nodes and recursively merging the rest.

Steps:

1. Compare the heads of list1 and list2.
2. The smaller node becomes the head of the merged list.
3. Recursively merge the remaining nodes.

Java Code

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;
    }
}

Complexity

• Time Complexity: O(n+m), due to recursive calls for each node.
• Space Complexity: O(n+m), for the recursion stack.

Merging Using a Priority Queue (Heap)

A priority queue can be used to efficiently merge the two lists by always extracting the smallest element from the heads of the lists.

Steps:

1. Insert all nodes from both lists into a priority queue.
2. Extract the nodes one by one from the queue and construct the merged list.

Java Code

import java.util.PriorityQueue;

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

    while (list1 != null) {
        minHeap.add(list1);
        list1 = list1.next;
    }

    while (list2 != null) {
        minHeap.add(list2);
        list2 = list2.next;
    }

    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;

    while (!minHeap.isEmpty()) {
        current.next = minHeap.poll();
        current = current.next;
    }

    return dummy.next;
}

Complexity

• Time Complexity: O((n+m)log⁡(n+m)), where n+m is the total number of nodes.
• Space Complexity: O(n+m), for the priority queue.

Divide and Conquer (Generalized for Multiple Lists) for Merge Two Sorted Lists

This approach is an extension of the merge process, particularly useful when merging more than two sorted lists.

Steps:

1. Treat list1 and list2 as part of a larger set of lists.
2. Merge them using the divide-and-conquer technique.
3. Continue merging until one list remains.

Java Code

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    while (lists.length > 1) {
        List<ListNode> mergedLists = new ArrayList<>();

        for (int i = 0; i < lists.length; i += 2) {
            ListNode l1 = lists[i];
            ListNode l2 = (i + 1 < lists.length) ? lists[i + 1] : null;
            mergedLists.add(mergeTwoLists(l1, l2));
        }

        lists = mergedLists.toArray(new ListNode[0]);
    }

    return lists[0];
}

private 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;
    }
}

Complexity

• Time Complexity: O(Nlog⁡K), where N is the total number of nodes and K is the number of lists.
• Space Complexity: O(1) for merging or O(K) for recursion.

By mastering the “Merge Two Sorted Lists“ problem, you’ll build a strong foundation in linked list manipulation and recursion. Whether you’re preparing for coding interviews or honing your problem-solving skills, this problem is an excellent choice.

Got any questions or alternate approaches? Let us know in the comments!