Loading...
Loading...
Merging two sorted linked lists looks simple — but most candidates fail on pointer bugs, space constraints, and missing edge cases. Here's how to nail it.
When an interviewer asks you to merge two sorted linked lists, they're not just checking if you can write a loop. They're watching for something much more specific — pointer manipulation skills, spatial reasoning, and whether you instinctively think about space optimization.
Here's what a strong answer signals to the interviewer:
A weak answer? Writing a solution that works but creates new nodes, or solving it by converting to an array and sorting again. Both of those tell the interviewer you're solving the symptom, not the problem.
You're given two linked lists, both already sorted in ascending order:
list1: 1 → 3 → 5
list2: 2 → 4 → 6Your job is to merge them into a single sorted list:
1 → 2 → 3 → 4 → 5 → 6Here's the constraint that trips up most candidates:
The result must be formed by splicing existing nodes together — not by creating new ones.
That one constraint is what separates a "it works" answer from a "strong hire" answer. Keep it in mind as we go.
If you've studied sorting algorithms, this should ring a bell immediately. This is exactly the merge step from merge sort — you've already seen it, you just haven't connected it to linked lists yet.
At every step, the logic is the same:
That last step — attaching the remainder — is where most candidates silently drop points. We'll get to that.
Let's walk through the approach you should reach for in an interview.
The dummy node is the secret weapon here. Instead of writing special-case logic to track the head of your result list, you create a throwaway node at the start. Your real answer starts at dummy.next. It's a small trick that eliminates an entire category of bugs.
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode runner = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
runner.next = list1; // reuse the node, don't copy it
list1 = list1.next;
} else {
runner.next =
Time complexity: O(n + m) — you visit every node exactly once.
Space complexity: O(1) — you're reusing existing nodes, not allocating new ones.
| Type | Complexity |
|---|---|
| Time | O(n + m) |
| Space | O(1) |
That space complexity is what interviewers are hoping to see. When you volunteer it unprompted, you're showing you think about efficiency as part of your design process — not as an afterthought.
I've watched hundreds of candidates stumble on this problem in ways that were totally avoidable. Here are the most common traps:
This is the most common mistake, and honestly, it's an easy one to make if you're nervous:
// ❌ Wrong — don't do this
runner.next = new ListNode(list1.val);This works functionally, but it violates the constraint. You're copying values instead of reusing nodes. The interviewer sees this and thinks: "They didn't read the problem carefully" or "They don't understand pointer manipulation yet."
Think of it this way — imagine you have two stacks of files on a desk. The problem asks you to interleave them into one stack. Creating new nodes is like photocopying all the files first. Wasteful and unnecessary.
Your while loop runs until one list hits null. But the other list still has nodes! A lot of candidates just return dummy.next at that point and miss half the data.
The fix is one line:
runner.next = (list1 != null) ? list1 : list2;Because both lists are already sorted, you don't need to iterate through the remainder. Every remaining node is already in the right order. Just attach the whole tail at once.
I've seen candidates try to track the head manually to avoid the dummy node — it always leads to a mess. Without it, you end up writing something like:
// Tedious and error-prone
ListNode head = null;
if (list1.val <= list2.val) {
head = list1;
list1 = list1.next;
} else {
head = list2;
list2 = list2.next;
}The dummy node is not a crutch — it's a standard pattern. Experienced engineers use it all the time. Using it in an interview shows pattern recognition, not weakness.
runner#This causes infinite loops, and it's brutal to debug under interview pressure:
// ❌ Missing this line turns your while loop into an infinite loop
runner = runner.next;If your code hangs on a test case, this is the first thing to check.
Some candidates see "linked list" and immediately think recursion, or convert both lists to arrays and sort them again. Both paths take longer, use more space, and — here's the thing most people miss — they signal to the interviewer that you didn't recognize the pattern.
When you see two sorted sequences and need to combine them, your brain should instantly say: merge sort merge step. That's the pattern.
Once you've nailed the iterative solution, the interviewer might ask: "Can you do this recursively?"
Here's what that looks like:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val <= list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
It's clean and elegant — almost beautiful, honestly. But here's the honest trade-off conversation you should have with the interviewer:
"The recursive version is more readable, but the call stack uses O(n + m) space in the worst case. For very long lists, we risk a stack overflow. The iterative version keeps space at O(1), which makes it safer for production use."
That kind of trade-off analysis is exactly what senior interviewers want to hear.
| Aspect | Iterative | Recursive |
|---|---|---|
| Space | O(1) | O(n + m) call stack |
| Readability | Good | Excellent |
| Production Safety | High | Stack overflow risk |
| Interview Preference | ✅ Preferred | ✅ Acceptable with trade-off discussion |
Here's the thing about linked list problems — the interviewer is listening to how you think, not just watching you type. Walking through your reasoning out loud separates great candidates from good ones.
Here's how an ideal walkthrough sounds:
"Okay, so I have two sorted lists. The constraint says I need to splice nodes, not create new ones — so I'll be doing pointer manipulation. This looks like the merge step in merge sort."
"I'll use a dummy node to avoid messy head-tracking logic. Then I'll use a runner pointer that walks through the result list as I build it."
"At each step, I compare the current heads of both lists, attach the smaller one to runner, and advance that list's pointer. After the loop, one list might still have nodes — since they're already sorted, I can just attach the tail directly."
"Time complexity is O(n + m) — one pass through both lists. Space is O(1) since I'm reusing existing nodes."
That's a complete, confident walkthrough. You covered the pattern recognition, the design choices, the complexity, and the key insight about the remaining tail — all before writing a line of code.
Strong candidates get follow-up questions. Here's what to expect and how to handle them:
"What if one or both lists are empty?"
Your dummy node approach handles this naturally — runner.next = list1 != null ? list1 : list2 covers the null case. Walk through a null input mentally to confirm.
"Can you do this recursively?" Yes! Present the recursive solution, then immediately volunteer the space trade-off without being asked.
"What if the lists have duplicate values?"
Your <= comparison already handles this correctly. Explain that equal values from list1 get priority, which is fine since order between equals doesn't matter here.
"How would you merge K sorted lists?" This is the big escalation. The right answer involves a min-heap (priority queue) or divide-and-conquer. Say: "I'd extend this by using a min-heap to always grab the smallest head across all K lists — that gives O(N log K) time." You don't need to code it on the spot; showing you know the direction is usually enough.
1→3 and 2→4) step by step. This catches the runner = runner.next bug before it bites you.Here's what to keep in mind when you walk into that interview:
runner.next = list1 not runner.next = new ListNode(list1.val).runner.next = (list1 != null) ? list1 : list2 is required — it's not optional cleanup.runner every iteration. Missing this line is the silent killer of linked list solutions.This problem comes up constantly — not just on its own, but as a building block inside harder problems like Merge K Sorted Lists and Sort List. Get this one clean and confident, and those bigger problems become a lot less intimidating.