Merging Two Sorted Linked List in Java

Blog Post: Merging Two Sorted Linked Lists - My In-Place Solution

When I first encountered the "Merge Two Sorted Lists" problem, I was excited to work with linked lists—a data structure that feels like a puzzle waiting to be solved. The task is straightforward: given the heads of two sorted linked lists, list1 and list2, merge them into one sorted list by splicing their nodes together. The catch? We need to preserve the sorted order while reusing the existing nodes. Let’s walk through my solution, explore how it works, and see why it’s a bit different from the typical approach.

Problem Breakdown

We’re given two singly-linked lists, each sorted in non-decreasing order. For example:

• list1 = [1, 2, 4]
• list2 = [1, 3, 4]

The goal is to produce a merged list like [1, 1, 2, 3, 4, 4]. The lists can be empty, and node values range from -100 to 100, with list lengths between 0 and 50. The problem hints at "splicing" nodes, suggesting we manipulate pointers rather than create an entirely new list from scratch.

Here’s the ListNode definition we’re working with:

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

My Solution

Here’s the code I came up with:

class Solution {
    public void printListNode(ListNode node) {
        while (node != null) {
            System.out.printf("%d ", node.val);
            node = node.next;
        }
        System.out.println();
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode last = null;
        ListNode curr1 = list1;
        ListNode curr2 = list2;

        while (curr1 != null && curr2 != null) {
            if (curr1.val <= curr2.val) {
                last = curr1;
                curr1 = curr1.next;                                
            } else {
                ListNode tmp = new ListNode(curr1.val);
                ListNode tmp_next = curr1.next;

                curr1.val = curr2.val;
                tmp.next = curr1.next;
                curr1.next = tmp;
                curr2 = curr2.next;
            }
        }

        while (curr2 != null) {
            last.next = curr2;
            last = last.next;
            curr2 = curr2.next;
        }

        return list1;
    }
}

How It Works

Let’s break this down step-by-step with the example list1 = [1, 2, 4] and list2 = [1, 3, 4].

1. Base Cases:

   • If list1 is null, return list2.
   • If list2 is null, return list1.
   • This handles empty list scenarios like [] and [0].

2. Initialization:

   • curr1 points to list1’s head (1).
   • curr2 points to list2’s head (1).
   • last tracks the last node we processed in list1, starting as null.

3. Main Loop:

   • Compare curr1.val (1) and curr2.val (1).
   • Since 1 <= 1, we keep curr1 as is, set last = curr1 (node 1), and move curr1 to 2.
   • Next iteration: curr1.val = 2, curr2.val = 1. Now 2 > 1, so we insert curr2’s value:
     • Create a new node tmp with curr1’s value (2).
     • Swap curr1.val to curr2.val (1), so curr1 becomes 1.
     • Link curr1.next to tmp (now 2), preserving the rest of the list.
     • Move curr2 to 3.
   • List now looks like: list1 = [1, 1, 2, 4], curr2 = [3, 4].

4. Continue Merging:

   • curr1 = 2, curr2 = 3. Since 2 <= 3, advance curr1 to 4, last to 2.
   • curr1 = 4, curr2 = 3. Since 4 > 3, insert 3:
     • tmp = 4, curr1.val = 3, curr1.next = tmp.
     • Move curr2 to 4.
   • List becomes: [1, 1, 2, 3, 4].

5. Append Remaining Nodes:

   • curr1 = 4, curr2 = 4. Since 4 <= 4, advance curr1 to null, last to 4.
   • curr1 is null, so append curr2 (4) to last.next.
   • Final list: [1, 1, 2, 3, 4, 4].

6. Return:

   • Return list1’s head.

Why This Approach?

Unlike the classic solution, which uses a dummy node and builds the list by picking the smaller value from either list, my approach modifies list1 in-place by inserting nodes from list2. It’s a trade-off:

• Pros: Reuses nodes and avoids creating a new list from scratch.
• Cons: Creates new nodes when inserting, slightly deviating from pure splicing.

Time and Space Complexity

• Time: O(n + m), where n and m are the lengths of list1 and list2. We traverse both lists once.
• Space: O(m), since we create new nodes for list2 elements when inserting. A pure splicing approach could achieve O(1) space.

Reflections

Looking back, my solution works but isn’t the most efficient for this problem. The standard approach—using two pointers and linking nodes directly—avoids new node creation. For a follow-up, I’d explore that method to align with the problem’s splicing hint. Still, this was a fun exercise in manipulating linked lists creatively!

What do you think—would you tackle it differently? Let me know in the comments!