The O(n) Club: Merge Two Sorted Linked Lists – The Dummy Node Sanity Check

The O(n) Club: Merge Two Sorted Linked Lists – The Dummy Node Sanity Check

⚡ TL;DR

Need to merge two sorted linked lists in Java? Skip the heroics—grab a dummy node, play connect-the-dots with your pointers, and don’t you dare make new nodes just to flex. The whole point is crisp, in-place merging. Here’s the gist:

// Java: merge by node splicing
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;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;

🧠 How Devs Usually Mess This Up

Ah, the classics! Most devs—possibly running on five cups of coffee and three hours of sleep—make lists explode with new nodes, totally missing that the interviewer wanted you to play pointer-Tetris, not buy new memory. Others panic and convert their lists into arrays (because that always fixes everything, right?), or they simply forget to tack on the leftovers, leading to tragically lost nodes. In summary: overkill, slow, and just a teensy bit wrong.

🔍 What’s Actually Going On

Think of two sorted conveyor belts (your lists), both feeding jelly beans to a quality control robot. The robot (your loop) always picks the next smallest candy and lines them up in the prettiest, single-file parade. Once one belt runs dry, the robot just dumps the rest from the other belt. The dummy node? That’s the robot’s clipboard—keeping track of where everything starts so you don’t lose your sweet, sweet list.

🛠️ PseudoCode

• Start with a dummy node: So you never lose your head (literally).

  ListNode dummy = new ListNode(-1);

• Keep a tail pointer for the new list: Your loyal assistant.

  ListNode tail = dummy;

• While both lists have goodies:
  • Compare the front values, pick the smaller (or tie, l1 wins),
  • Splice it onto tail.next,
  • Advance pointers correctly.

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

• One list is empty? Just glue the non-empty leftovers on.

  tail.next = (l1 != null) ? l1 : l2;

• Return the merged head: But not the dummy—he’s just the doorman.

  return dummy.next;

💻 The Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 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;
    }
    tail.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Input lists might be empty? Chill. Dummy node’s still got this. It works if one or both lists are null. No NPEs, no drama.
• Don’t make new nodes: If you do, you’re doubling RAM for no reason. Splice, don’t clone.
• Attach the leftovers or risk losing half your work. The last pointer sets the stragglers loose if you forget this.
• Prefer iteration over recursion: Recursion is fancy for small lists but turns into a stack-eating monster on big ones (ask system admins why that’s bad).
• Time Complexity: O(n + m), every node visited exactly once.
• Space Complexity: O(1)—just some pointer acrobatics, unless you go recursive, in which case enjoy your O(n + m) call stack disaster.

🧠 Interviewer Brain-Tattoo

If you don’t use a dummy node, Java will let you—right up until you wish you’d brought one. Merge responsibly!