Merge Two Sorted Lists

Merging two sorted linked lists is like merging two sorted streams of data—think combining two user event logs in chronological order. It’s a common real-world task and a perfect interview warm-up to test your pointer and list-manipulation skills.

Problem Statement

Given the heads of two sorted singly linked lists l1 and l2, merge them into one sorted list by reusing the existing nodes. Return the head of the merged list.

// ListNode definition provided in interview
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// Function signature
public ListNode mergeTwoLists(ListNode l1, ListNode l2);

1. Clarify Requirements Before Jumping Into Code

I’ll make sure I understand exactly:

• Both l1 and l2 are sorted in ascending order.

• I should link existing nodes, not create new nodes if possible.

• Returning the merged head is enough—no need to return both lists.

• It’s fine to use a dummy/sentinel node for ease.

• Input lists may be null (empty).

2. Identify the Category of the Question

This is a linked-list merging problem using the two-pointer or merge-step pattern. Common linked-list patterns include:

• Two-pointer merging (this problem)

• Fast/slow pointer for cycle detection or middle finding

• Pointer reversal for reversing lists

• Dummy-head technique for building new lists

• Recursive list processing

Merging sorted lists is the canonical two-pointer merge.

3. Consider a Brute-Force Approach to Understand the Problem

A very brute approach:

1. Copy all values from l1 and l2 into an array.

2. Sort the array.

3. Rebuild a new linked list from the sorted values.

4. Time: O((n+m) log(n+m)) for sorting

5. Space: O(n+m) for array and new nodes

6. Drawbacks: Violates in-place requirement and uses extra space

Still, this confirms the sorted-output requirement.

4. Brainstorm More Solutions

I want O(n+m) time and O(1) extra space. Possible paths:

• Recursive merge: Compare heads of l1 and l2. Whichever is smaller becomes new head; recursively merge its next with the other list. This uses O(n+m) time and O(n+m) stack space in the worst case.

• Iterative merge with dummy: Start with a dummy node and maintain a pointer to the tail of the linked list. While both lists have nodes, compare l1.val and l2.val. Link the smaller node to tail.next, then advance that list and tail. Finally, attach the non-empty remainder. This is O(n+m) time and O(1) extra space.

• In-place pointer weaving: Without a dummy, handle the head pointer assignment specially, then weave pointers similarly. More error-prone.

Thinking through these, iterative with a dummy head is straightforward and safe. It naturally handles empty lists and builds the result in one pass.

5. Discuss Trade-Offs Between Your Solutions

Approach	Time	Space	Pros	Cons
Array + Sort + Rebuild	O((n+m)log(n+m))	O(n+m)	Very simple	Extra space, extra node creation
Recursive Merge	O(n+m)	O(n+m) stack	Clean, concise	Risk of stack overflow
Iterative Dummy Merge	O(n+m)	O(1)	In-place, constant extra memory, safe	Slight pointer logic required

Iterative dummy-merge is optimal for in-place, linear-time merging without recursion overhead.

6. Write Pseudocode to Structure Your Thoughts

function mergeTwoLists(l1, l2):
  create dummy = new ListNode(-1)
  tail = dummy

  while l1 != null and l2 != null:
    if l1.val <= l2.val:
      tail.next = l1
      l1 = l1.next
    else:
      tail.next = l2
      l2 = l2.next
    tail = tail.next

  // attach remainder
  if l1 != null:
    tail.next = l1
  else:
    tail.next = l2

  return dummy.next

7. Consider Edge Cases

• Both lists empty → return null.

• One list empty → return the other list unchanged.

• All values in one list smaller → entire second list attaches at the end.

• Interleaved values → pointers alternate correctly.

• Duplicate values equal → maintain original relative order by using <=.

8. Write Full Code Syntax

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode tail = dummy;

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

        // Attach the non-empty list, if any
        if (l1 != null) {
            tail.next = l1;
        } else {
            tail.next = l2;
        }

        return dummy.next;
    }
}

9. Test Your Code

public static void main(String[] args) {
    Solution sol = new Solution();

    // Helper to build lists: buildList(1,2,4) => 1->2->4
    // and printList to display results (omitted for brevity)

    // Test 1: both empty
    assert sol.mergeTwoLists(null, null) == null;

    // Test 2: one empty
    ListNode a = buildList(1,3,5);
    assert equalLists(sol.mergeTwoLists(a, null), a);

    // Test 3: disjoint ranges
    ListNode l1 = buildList(1,2,3);
    ListNode l2 = buildList(4,5,6);
    assert equalLists(sol.mergeTwoLists(l1, l2), buildList(1,2,3,4,5,6));

    // Test 4: interleaved
    ListNode l3 = buildList(1,4,7);
    ListNode l4 = buildList(2,3,8);
    assert equalLists(sol.mergeTwoLists(l3, l4), buildList(1,2,3,4,7,8));

    // Test 5: duplicates
    ListNode l5 = buildList(1,1,2);
    ListNode l6 = buildList(1,3);
    assert equalLists(sol.mergeTwoLists(l5, l6), buildList(1,1,1,2,3));

    System.out.println("All tests passed!");
}

10. Key Lessons to Remember for Future Questions

• Dummy head technique simplifies list-building and avoids special-case head management.

• Iterative solutions avoid recursion depth issues—prefer them for long lists.

Good Luck and Happy Coding!