LeetCode Problem 21: Merge Two Sorted Lists Using An Iterative Approach (Java Solution)

Problem Overview

Given two sorted linked lists, merge them into a single sorted linked list by splicing their nodes together. This problem tests your understanding of linked list manipulation and is a common interview question.

Example:
Input: l1 = [1,2,4], l2 = [1,3,5]
Output: [1,1,2,3,4,5]
Explanation: Nodes are combined in ascending order.

Why Use an Iterative Approach with a Dummy Node?

The iterative method efficiently merges the two lists in O(m + n) time (where m and n are the list lengths) using constant space (O(1)). A dummy node simplifies edge cases (e.g., empty lists) and avoids redundant checks.

Key Advantages:

No extra space: Unlike recursion, this avoids stack overhead.
Single pass: Each node is processed exactly once.

Step-by-Step Solution

Algorithm Steps:

Initialize a Dummy Node: Acts as a placeholder to start the merged list.
Compare and Link Nodes: Iterate through both lists, appending the smaller node to the merged list.
Attach Remaining Nodes: Link any leftover nodes once one list is exhausted.

Java Solution Code

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

        ListNode dummyHead = new ListNode(-1); // Dummy starter node
        ListNode tail = dummyHead;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tail.next = l1;
                l1 = l1.next;
            } else {
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next; // Move tail forward
        }

        // Attach remaining nodes
        tail.next = (l1 != null) ? l1 : l2;

        return dummyHead.next;
    }
}

Code Explanation

1. Edge Case Handling

If either list is empty, return the other list directly.

2. Dummy Node Initialization

dummyHead simplifies list construction by providing an initial node.
tail always points to the end of the merged list for easy appending.

3. Node Comparison and Linking

Compare l1.val and l2.val at each step.
Attach the smaller node to tail.next and advance the corresponding list pointer.
Move tail forward to the newly added node.

4. Handling Remaining Nodes

After the loop, one list may still have nodes. Link them directly to tail.next.

Complexity Analysis

Time Complexity: O(m + n) – Each node is visited once.
Space Complexity: O(1) – Only a few pointers are used.

Visualizing the Process

Example: l1 = [1 → 2 → 4], l2 = [1 → 3 → 5]

Step 1: Compare 1 (l1) and 1 (l2). Attach 1 from l2.

Merged list: [-1 → 1]

Step 2: Compare 1 (l1) and 3 (l2). Attach 1 from l1.

Merged list: [-1 → 1 → 1]

Step 3: Compare 2 (l1) and 3 (l2). Attach 2.

Merged list: [-1 → 1 → 1 → 2]

Continue until all nodes are linked.

Common Pitfalls and Tips

Forgetting Edge Cases: Always check if input lists are empty.
Updating Pointers Correctly: Ensure l1, l2, and tail move forward properly.
Memory Efficiency: Avoid creating new nodes; reuse existing ones.

Conclusion

The iterative dummy node approach is optimal and intuitive for merging sorted linked lists. It’s a fundamental technique for solving more complex problems like merging k sorted lists or sorting algorithms.

Practice Similar Problems:

Stuck or have questions? Let me know in the comments! 🔥

Keywords: merge two sorted linked lists, LeetCode problem 21 solution, Java iterative approach, dummy node technique, linked list merging algorithm, coding interview preparation, optimize linked list operations.

LeetCode Problem 21: Merge Two Sorted Lists Using an Iterative Approach (Java Solution)