Merge Two Sorted Lists

Problem Statement

Write a Java program that merges two sorted singly linked lists into a single sorted linked list. Each linked list consists of nodes containing integer values in non-decreasing order. The program should merge the lists by comparing node values and constructing a new sorted list, preserving the sorted order. Test the implementation with different inputs, including empty lists, single-node lists, lists of varying lengths, and lists with duplicate values. You can visualize this as combining two sorted stacks of numbered cards into one sorted stack, picking the smaller card from the top of either stack each time.

Input:

• Two sorted singly linked lists of integers (e.g., 1→3→5 and 2→4→6). Output: A single sorted linked list as a string (e.g., "1 2 3 4 5 6"). Constraints:
• The list sizes are between 0 and 10^5.
• Node values are integers in the range [-10^9, 10^9].
• Both lists are sorted in non-decreasing order.
• Either or both lists may be empty. Example:
• Input: list1 = 1→3→5, list2 = 2→4→6
• Output: "1 2 3 4 5 6"
• Explanation: Merges into a sorted list 1→2→3→4→5→6.
• Input: list1 = [], list2 = []
• Output: "[]"
• Explanation: Merging two empty lists results in an empty list.
• Input: list1 = 1→1, list2 = 1→2
• Output: "1 1 1 2"
• Explanation: Merges lists with duplicates into a sorted list.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION mergeTwoLists(list1, list2)
    CREATE dummy as new Node(0)
    SET tail to dummy
    SET current1 to list1
    SET current2 to list2
    WHILE current1 is not null AND current2 is not null
        IF current1.value <= current2.value THEN
            SET tail.next to current1
            SET current1 to current1.next
        ELSE
            SET tail.next to current2
            SET current2 to current2.next
        ENDIF
        SET tail to tail.next
    ENDWHILE
    IF current1 is not null THEN
        SET tail.next to current1
    ELSE IF current2 is not null THEN
        SET tail.next to current2
    ENDIF
    RETURN dummy.next
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current is not null
        APPEND current.value to result
        IF current.next is not null THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of pairs of linked lists
    FOR each testCase in testCases
        PRINT test case details
        CALL mergeTwoLists(testCase.list1, testCase.list2)
        PRINT merged list using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
2. In mergeTwoLists: a. Create a dummy node to simplify list construction. b. Initialize tail to dummy, current1 to list1, current2 to list2. c. While both lists have nodes:
   • Compare current1.value and current2.value.
   • Append smaller node to tail.next, advance corresponding pointer.
   • Move tail to appended node. d. Append remaining nodes from list1 or list2, if any. e. Return dummy.next as the merged list head.
3. In toString: a. If head is null, return "[]". b. Traverse the list, append each value to a StringBuilder with spaces. c. Return the string representation.
4. In main, test with non-empty lists, empty lists, single-node lists, and lists with duplicates.

Java Implementation

public class MergeTwoSortedLists {
    // Node class for the linked list
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    // Merges two sorted linked lists
    public Node mergeTwoLists(Node list1, Node list2) {
        Node dummy = new Node(0);
        Node tail = dummy;
        Node current1 = list1;
        Node current2 = list2;

        while (current1 != null && current2 != null) {
            if (current1.value <= current2.value) {
                tail.next = current1;
                current1 = current1.next;
            } else {
                tail.next = current2;
                current2 = current2.next;
            }
            tail = tail.next;
        }

        if (current1 != null) {
            tail.next = current1;
        } else if (current2 != null) {
            tail.next = current2;
        }

        return dummy.next;
    }

    // Converts linked list to string for output
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node list1;
        Node list2;

        TestCase(int[] values1, int[] values2) {
            // Create list1
            if (values1.length == 0) {
                list1 = null;
            } else {
                list1 = new Node(values1[0]);
                Node current = list1;
                for (int i = 1; i < values1.length; i++) {
                    current.next = new Node(values1[i]);
                    current = current.next;
                }
            }
            // Create list2
            if (values2.length == 0) {
                list2 = null;
            } else {
                list2 = new Node(values2[0]);
                Node current = list2;
                for (int i = 1; i < values2.length; i++) {
                    current.next = new Node(values2[i]);
                    current = current.next;
                }
            }
        }
    }

    // Main method to test merging sorted lists
    public static void main(String[] args) {
        MergeTwoSortedLists merger = new MergeTwoSortedLists();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 3, 5}, new int[]{2, 4, 6}), // Both non-empty
            new TestCase(new int[]{}, new int[]{}),              // Both empty
            new TestCase(new int[]{1}, new int[]{}),            // One empty
            new TestCase(new int[]{1, 1}, new int[]{1, 2}),     // Duplicates
            new TestCase(new int[]{1, 2, 3}, new int[]{4})      // Different lengths
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("List 1: " + merger.toString(test.list1));
            System.out.println("List 2: " + merger.toString(test.list2));
            Node merged = merger.mergeTwoLists(test.list1, test.list2);
            System.out.println("Merged list: " + merger.toString(merged) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
List 1: 1 3 5
List 2: 2 4 6
Merged list: 1 2 3 4 5 6

Test case 2:
List 1: []
List 2: []
Merged list: []

Test case 3:
List 1: 1
List 2: []
Merged list: 1

Test case 4:
List 1: 1 1
List 2: 1 2
Merged list: 1 1 1 2

Test case 5:
List 1: 1 2 3
List 2: 4
Merged list: 1 2 3 4

Explanation:

• Test case 1: Merges 1→3→5 and 2→4→6 into 1→2→3→4→5→6.
• Test case 2: Both empty lists result in an empty list.
• Test case 3: Merges 1 with empty list, resulting in 1.
• Test case 4: Merges lists with duplicates 1→1 and 1→2 into 1→1→1→2.
• Test case 5: Merges 1→2→3 and 4 into 1→2→3→4.

How It Works

• Node: Stores an integer value and a next pointer.
• mergeTwoLists:
  • Uses a dummy node to simplify list construction.
  • Compares nodes from both lists, appending the smaller to the result.
  • Advances the corresponding list’s pointer and moves the tail.
  • Appends any remaining nodes from either list.
• toString: Converts the list to a space-separated string, returning "[]" for empty lists.
• Example Trace (Test case 1):
  • list1: 1→3→5, list2: 2→4→6.
  • dummy→null, tail=dummy, current1=1, current2=2.
  • Step 1: 1≤2, dummy→1, current1=3, tail=1.
  • Step 2: 3>2, dummy→1→2, current2=4, tail=2.
  • Step 3: 3≤4, dummy→1→2→3, current1=5, tail=3.
  • Step 4: 5>4, dummy→1→2→3→4, current2=6, tail=4.
  • Step 5: 5≤6, dummy→1→2→3→4→5, current1=null, tail=5.
  • Step 6: Append 6, dummy→1→2→3→4→5→6.
  • Return: 1→2→3→4→5→6.
• Main Method: Tests non-empty lists, empty lists, one empty list, duplicates, and different lengths.

Complexity Analysis Table

Note:

• n and m are the lengths of the two input lists.
• Time complexity: O(n + m) for merging (single pass through both lists); O(n) for toString (traverse list).
• Space complexity: O(1) for merging (constant pointers); O(n) for toString (StringBuilder).
• Worst case: O(n + m) time, O(n + m) space for output with large lists.

✅ Tip: Use a dummy node to simplify merging by avoiding special cases for the head. Compare values iteratively to maintain sorted order.

⚠ Warning: Ensure pointers are updated correctly to avoid losing list segments. Handle empty list cases to prevent null pointer exceptions.