Java Program to Merge Two Sorted Linked Lists

You can merge two sorted linked lists in Java by comparing their nodes one by one and linking the smaller node to the merged list using a method like mergeTwoLists(ListNode l1, ListNode l2) that returns the head of the merged sorted list.

Examples

InputList1: 1->3->5, List2: 2->4->6

OutputMerged List: 1->2->3->4->5->6

InputList1: 1->2->4, List2: 1->3->4

OutputMerged List: 1->1->2->3->4->4

InputList1: empty, List2: 0->7->8

OutputMerged List: 0->7->8

How to Think About It

To merge two sorted linked lists, start by comparing the first nodes of both lists. Attach the smaller node to a new merged list and move that list's pointer forward. Repeat this until one list is empty, then attach the remaining nodes of the other list to the merged list.

Algorithm

1

Create a dummy node to start the merged list.

2

Use a pointer to track the current end of the merged list.

3

While both lists have nodes, compare their current nodes.

4

Attach the smaller node to the merged list and move that list's pointer forward.

5

After the loop, attach the remaining nodes of the non-empty list to the merged list.

6

Return the node next to the dummy node as the head of the merged list.

Code

java

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

public class MergeSortedLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        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;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        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);

        ListNode merged = mergeTwoLists(l1, l2);
        System.out.print("Merged List: ");
        printList(merged);
    }
}

Output

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

Dry Run

Let's trace merging List1: 1->3->5 and List2: 2->4->6 through the code

1

Initialize dummy and current

dummy=0->null, current points to dummy

2

Compare l1=1 and l2=2

1 < 2, attach l1 node (1), move l1 to 3

3

Compare l1=3 and l2=2

2 < 3, attach l2 node (2), move l2 to 4

4

Compare l1=3 and l2=4

3 < 4, attach l1 node (3), move l1 to 5

5

Compare l1=5 and l2=4

4 < 5, attach l2 node (4), move l2 to 6

6

Compare l1=5 and l2=6

5 < 6, attach l1 node (5), move l1 to null

7

l1 is null, attach remaining l2 nodes

Attach l2 node (6)

Current merged list
0->1
0->1->2
0->1->2->3
0->1->2->3->4
0->1->2->3->4->5
0->1->2->3->4->5->6

Why This Works

Step 1: Use a dummy node

A dummy node simplifies edge cases by providing a fixed starting point for the merged list.

Step 2: Compare nodes one by one

By always choosing the smaller node, the merged list remains sorted.

Step 3: Attach remaining nodes

Once one list is empty, the rest of the other list is already sorted and can be attached directly.

Alternative Approaches

Recursive merge

java

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

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        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);

        ListNode merged = mergeTwoLists(l1, l2);
        System.out.print("Merged List: ");
        printList(merged);
    }
}

This method is elegant and concise but uses extra stack space due to recursion.

Create new list nodes

java

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

public class MergeSortedLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                current.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            current = current.next;
        }
        while (l1 != null) {
            current.next = new ListNode(l1.val);
            l1 = l1.next;
            current = current.next;
        }
        while (l2 != null) {
            current.next = new ListNode(l2.val);
            l2 = l2.next;
            current = current.next;
        }
        return dummy.next;
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print("->");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        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);

        ListNode merged = mergeTwoLists(l1, l2);
        System.out.print("Merged List: ");
        printList(merged);
    }
}

This approach creates new nodes instead of reusing existing ones, using more memory but preserving original lists.

Complexity: O(n + m) time, O(1) space

Time Complexity

The algorithm visits each node of both lists once, so the time is proportional to the total number of nodes, O(n + m).

Space Complexity

It uses constant extra space by rearranging pointers without creating new nodes, so space is O(1).

Which Approach is Fastest?

The iterative approach is fastest and uses less memory than recursion, which adds call stack overhead.

Approach	Time	Space	Best For
Iterative merge	O(n + m)	O(1)	Efficient in time and memory
Recursive merge	O(n + m)	O(n + m)	Cleaner code but uses stack space
Create new nodes	O(n + m)	O(n + m)	Preserves original lists but uses more memory