Merge Two Sorted Linked Lists - Data Structures and Algorithms (DSA) Guide

Problem Statement

You are given two sorted linked lists, and your task is to merge them into one sorted linked list. Your return list should be made by splicing together the nodes of the two lists.

Example:

Given the lists:
List1: 1 -> 3 -> 5
List2: 2 -> 4 -> 5
Merged Result: 1 -> 2 -> 3 -> 4 -> 5 -> 5

Intuition

Imagine you have two piles of numbered cards, both sorted in ascending order. You want to combine them into a single sorted pile. You would likely compare the top card from each pile at every step, picking the smaller one to place in your final pile. This problem follows a similar thought process.

Brute Force Solution

A naive approach would involve combining the two lists and then sorting the resultant list. While straightforward, this approach doesn’t make use of the fact that the two lists are already sorted.

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

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    List<Integer> combined = new ArrayList<>();
    
    // Add all elements of l1 to the list
    while(l1 != null) {
        combined.add(l1.val);
        l1 = l1.next;
    }

    // Add all elements of l2 to the list
    while(l2 != null) {
        combined.add(l2.val);
        l2 = l2.next;
    }

    // Sort the list
    Collections.sort(combined);

    // Convert the list to a linked list and return
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    for (int val : combined) {
        current.next = new ListNode(val);
        current = current.next;
    }
    return dummy.next;
}

Optimal Solution

A more efficient approach leverages the idea of pointers or recursion. We can maintain a reference to each list and compare the current nodes’ values. This way, we can build the merged list node by node, ensuring order.

Iterative Solution (using pointers):

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Dummy node to act as the start of the result list
    ListNode dummy = new ListNode(-1);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // If one list is exhausted, the other still may have elements. Attach it to the result list.
    if (l1 != null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next;
}

Recursive Solution:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;

    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

Merging two sorted lists is a common interview problem that not only tests one’s understanding of linked lists but also the ability to come up with optimized solutions by recognizing patterns