How Merge Two Sorted Linked Lists Work? Explained with Examples

Merging two sorted linked lists creates a single sorted linked list by integrating the nodes from both lists. By comparing elements from both lists one at a time and allocating them appropriately, the objective is to generate a new list that keeps the sorted order, which is previously done for each input list. Data structures and linked list manipulation both heavily rely on this procedure, which is frequently utilized in algorithms such as merge sort.

Problem Statement Example

Given two singly linked lists that are already sorted in ascending order, the goal is to merge two sorted linked lists into a single sorted list. Instead of creating new nodes, the existing nodes should be rearranged by adjusting their pointers.

Input:

• List 1:

1 → 3 → 5

• List 2:

2 → 4 → 6

Output:

Merged List:

1 → 2 → 3 → 4 → 5 → 6

A linked list is a linear data structure where elements (called nodes) are linked together using pointers. Unlike arrays, linked lists allow dynamic memory allocation and efficient insertions or deletions. When you need to merge sorted linked lists, the ability to manipulate pointers directly makes the process efficient. Each node contains:

• Data: The actual value stored in the node.
• Next Pointer: A link that connects a node to the following node in a linked list.

One way to merge a sorted linked list is by converting the linked lists into arrays. First, extract all node values into an array, then sort it, and finally create a new linked list from the sorted values. However, it can be useful in systems where sorting is needed separately before merging.

Merge Two Sorted Linked Lists Java Code Example:

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeSortedLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        List<Integer> values = new ArrayList<>();
        
        // Extract values from both linked lists
        while (l1 != null) {
            values.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            values.add(l2.val);
            l2 = l2.next;
        }
        
        // Sort the combined list
        Collections.sort(values);
        
        // Create a new sorted linked list
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        for (int val : values) {
            current.next = new ListNode(val);
            current = current.next;
        }
        
        return dummy.next;
    }
    
    // Utility function to print linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }
    
    public static void main(String[] args) {
        // Example usage
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        
        System.out.println("Merged Sorted List:");
        ListNode mergedList = mergeTwoLists(l1, l2);
        printList(mergedList);
    }
}

Explanation

The merge two sorted linked lists method converts the linked lists into an array, merges the elements, and sorts the final result. After sorting, a new linked list is created from the sorted values. This method ensures an ordered merge without modifying the original lists.

Output

Merged Sorted List:  
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null  

Time and Space Complexity:

• Time Complexity: O((n+m)log⁡(n+m)) (due to sorting)
• Space Complexity: O(n+m) (storing all elements in an array)

The recursive approach to merge sorted linked lists works by choosing the smaller head node first and then calling the function again to merge the remaining nodes. It’s simple and keeps the order intact, but it uses extra memory due to recursive calls. This approach is best for smaller lists where stack space isn’t a problem.

Merge Two Sorted Linked Lists Java Code Example:

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeSortedLists {
    public static 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;
        }
    }
    
    // Utility function to print linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }
    
    public static void main(String[] args) {
        // Example usage
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        
        System.out.println("Merged Sorted List:");
        ListNode mergedList = mergeTwoLists(l1, l2);
        printList(mergedList);
    }
}

Explanation

This approach recursively compares the heads of both linked lists, selecting the smaller value and advancing its list. The process continues until one list is empty, at which point the remaining nodes from the other list are attached. This approach ensures a smooth merge of two sorted linked lists while preserving their order effectively.

Output

Merged Sorted List:  
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null  

Time and Space Complexity:

• Time Complexity: O(n+m) (each node is visited once)
• Space Complexity: O(n+m) (recursion stack)

A simple way to merge two sorted linked lists is by using a dummy node. This placeholder helps build the merged list by comparing nodes from both lists and linking the smaller one each time. The process continues until all nodes are merged.

Merge Two Sorted Linked Lists Java Code Example:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class IterativeMerge {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;
        
        // Merge both lists in sorted order
        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;
        }
        
        // Attach the remaining part of the non-empty list
        current.next = (l1 != null) ? l1 : l2;
        
        return dummy.next;
    }
    
    // Utility function to print linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }
    
    public static void main(String[] args) {
        // Example usage
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        
        System.out.println("Merged Sorted List:");
        ListNode mergedList = mergeTwoLists(l1, l2);
        printList(mergedList);
    }
}

Explanation

This method uses a dummy node to merge two sorted linked lists efficiently in one pass, keeping the process structured and seamless. It moves through both lists, connecting the smaller node at each step and appending any leftover nodes once one list is exhausted.

Output

Merged Sorted List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Time and Space Complexity:

• Time Complexity: O(n+m) (single pass through both lists)
• Space Complexity: O(1) (modifies pointers without extra memory)

Another way to merge two sorted linked lists is by adjusting pointers directly instead of using extra space. This method compares nodes and rearranges the next pointers to form a single sorted list.

Merge Two Sorted Linked Lists Java Code Example:

import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeSortedLists {
    public static ListNode mergeInPlace(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val > l2.val) {
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        
        ListNode res = l1;
        while (l1 != null && l2 != null) {
            ListNode prev = null;
            while (l1 != null && l1.val <= l2.val) {
                prev = l1;
                l1 = l1.next;
            }
            prev.next = l2;
            
            // Swap l1 and l2
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        return res;
    }
    
    // Utility function to print linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("null");
    }
    
    public static void main(String[] args) {
        // Example usage
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);
        
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);
        
        System.out.println("Merged Sorted List (In-Place):");
        ListNode mergedList = mergeInPlace(l1, l2);
        printList(mergedList);
    }
}

Explanation

This approach merges two sorted linked lists without using extra space. By rearranging pointers in place, it efficiently merges two sorted linked lists while maintaining a reference to the smaller node and adjusting the next pointers accordingly. This reduces memory usage while ensuring the lists remain sorted.

Output

Merged Sorted List (In-Place):  
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null  

Time and Space Complexity:

• Time Complexity: O(n+m) (each node is processed once)
• Space Complexity: O(1) (no extra storage used)

1. Database Management

Databases use indexing to store and retrieve data efficiently. When querying large datasets, techniques like merge sorted linked list operations help merge sorted records from multiple index pages, maintaining order and speeding up searches. This approach optimizes query performance, reduces redundancy, and ensures seamless data retrieval in applications like e-commerce, banking, and enterprise software.

2. Real-Time Data Processing

Industries that depend on continuous data streams, such as finance, social media, and IoT, need efficient ways to merge and process ordered data. Techniques like Merge Two Sorted Linked Lists help streamline this process, enabling real-time analytics. This allows businesses to track trends, detect anomalies, and make data-driven decisions effectively.

3. Version Control Systems

Software development tools like Git use merging techniques to integrate changes from multiple contributors. When different developers modify the same file, merging sorted lists ensures a structured and conflict-free version. This process is essential in maintaining code integrity, streamlining collaboration, and preventing errors in large-scale software projects.

Merging two sorted linked lists is a critical problem in computer science with various solutions. The simplest methods to merge two sorted linked lists use recursion or iteration, while in-place merging optimizes memory usage. Sorting-based approaches work, but are less efficient. These techniques are used in databases, data processing, and version control. Choosing the right method depends on efficiency and memory constraints.

1. What is the most efficient way to merge two sorted linked lists?

The iterative approach using a dummy node is the most efficient. It runs in O(n + m) time and O(1) space by comparing nodes and attaching the smaller one to the merged list. This avoids unnecessary memory usage and ensures an optimal merge.

2. How does the recursive approach work for merging two sorted linked lists?

The recursive method selects the smaller head node and merges the remaining elements recursively. It is concise but has O(n + m) space complexity due to recursive stack calls. While elegant, it can be inefficient for very long lists.

3. What are the edge cases to consider when merging two sorted linked lists?

Edge cases include one or both lists being empty, lists of different lengths, and handling duplicate values. The algorithm should correctly link nodes while maintaining sorted order without unnecessary modifications.

4. Can we merge two sorted linked lists in-place without using extra space?

Yes, merging can be done in-place by directly adjusting pointers instead of creating new nodes. This approach eliminates extra space usage but requires careful pointer handling to avoid breaking the list structure.

5. What is the difference between merging sorted arrays and merging sorted linked lists?

Merging arrays requires O(n + m) extra space to store the result, while linked lists can be merged in O(1) extra space by modifying pointers. Linked lists also allow efficient insertions without shifting elements like arrays.

6. How do you handle merging K-sorted linked lists instead of just two?

Using a min-heap (priority queue) is the most efficient method, running in O(n log k) time. Another approach is merging lists pair by pair, but it is less efficient. The heap-based method ensures optimal performance.

7. What are some real-world applications of merging sorted linked lists?

This technique is used in real-time data merging, database indexing, and version control (e.g., Git). It helps efficiently combine sorted data streams, ensuring the smooth integration of structured information.