Merge two sorted linked lists into one

You are ten minutes into your Google phone screen, and the interviewer asks you to merge two sorted linked lists into one. It sounds straightforward, but the follow-up questions are where things get real: "Can you do it in constant space? What if one list is empty? How does this generalize to K lists?" This problem, also known as "Merge Two Sorted Lists" on other platforms, is a staple at companies like Adobe, Amazon, Google, and Meta. It tests your comfort with pointer manipulation and your ability to handle edge cases cleanly.

TL;DR

Use a dummy node and a current pointer. Compare the heads of both lists, attach the smaller node to current.next, and advance that list's pointer. When one list is exhausted, attach the remainder of the other. Return dummy.next. This runs in O(m + n) time and O(1) space because you are splicing existing nodes rather than allocating new ones.

Why This Problem Matters

Merging two sorted lists is the core operation behind merge sort and a building block for harder problems like merging K sorted lists or flattening a sorted linked-list structure. It appears frequently in interviews because it combines pointer manipulation with careful edge-case handling in a compact problem. Get this right, and you will have a pattern you can reuse across many linked-list questions.

Linked Lists: Quick Refresher

A singly linked list is a chain of nodes where each node stores a value and a reference to the next node. The last node points to null.

Key properties:

• Head: the first node in the list
• Tail: the last node, pointing to null
• Sequential access: you must traverse from the head to reach any node
• Pointer-based: nodes can be anywhere in memory, connected only by references

Understanding the Problem

Given: the heads of two sorted linked lists, list1 and list2 Task: merge them into a single sorted list by splicing nodes together Return: the head of the merged list

Here are our two input lists:

list1:

list2:

After merging:

The merged list contains every node from both inputs, in sorted order. Notice that we are not creating new nodes. We are redirecting the next pointers of existing nodes to form one continuous chain.

Edge Cases

1. Both lists empty: return null
2. One list empty: return the other list as-is
3. Lists of different lengths: the longer list's remaining nodes get attached at the end
4. Duplicate values: handled naturally by the comparison (list1.data ≤ list2.data picks list1 on ties)

Solution Approach

The idea is simple: walk through both lists simultaneously, always picking the smaller current node and appending it to the merged result. A dummy node at the front eliminates special-case logic for initializing the head.

The Dummy Node Technique

Without a dummy node, you would need conditional logic to decide what the head of the merged list is before the main loop even starts. The dummy node sidesteps this. You create a placeholder node, build the merged list after it, and return dummy.next at the end.

Step-by-Step Walkthrough

For list1 = [1, 2, 4] and list2 = [1, 3, 4]:

Initialize: create dummy node (0) and set current = dummy.

Iteration 1: Compare list1(1) vs list2(1). Since 1 ≤ 1, attach list1's node. Advance list1 to 2.

Iteration 2: Compare list1(2) vs list2(1). Since 2 > 1, attach list2's node. Advance list2 to 3.

Iteration 3: Compare list1(2) vs list2(3). Since 2 ≤ 3, attach list1's node. Advance list1 to 4.

Iteration 4: Compare list1(4) vs list2(3). Since 4 > 3, attach list2's node. Advance list2 to 4.

Iteration 5: Compare list1(4) vs list2(4). Since 4 ≤ 4, attach list1's node. list1 is now exhausted.

Attach remainder: list2 still has node 4. Attach it directly.

Return dummy.next, which skips the placeholder 0 and gives us [1, 1, 2, 3, 4, 4].

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    // Create a dummy node to simplify head initialization
    ListNode dummy = new ListNode(0);
    // current tracks the tail of the merged list
    ListNode current = dummy;

    // Compare and attach the smaller node at each step
    while (list1 != null && list2 != null) {
      if (list1.data <= list2.data) {
        current.next = list1;
        list1 = list1.next;
      } else {
        current.next = list2;
        list2 = list2.next;
      }
      current = current.next;
    }

    // Attach whichever list still has remaining nodes
    if (list1 != null) {
      current.next = list1;
    } else {
      current.next = list2;
    }

    // Skip the dummy and return the real head
    return dummy.next;
  }
}

Each iteration does a constant amount of work: one comparison, one pointer reassignment, and one advance. The loop terminates as soon as either list runs out, and the leftover nodes are attached in O(1).

Alternating Merge Example

When the values interleave perfectly, the algorithm alternates between the two lists:

list1:

list2:

Merged:

This is the worst case for the number of comparisons, but the time complexity remains O(m + n).

Complexity Analysis

Time Complexity: O(m + n)

Each node from list1 and list2 is processed exactly once. At each step, the algorithm performs a single comparison and a constant number of pointer operations. With m and n being the lengths of the two lists, the total work is proportional to m + n.

Space Complexity: O(1)

The algorithm uses only a fixed number of extra variables (dummy, current) regardless of input size. No new nodes are allocated. The existing nodes are simply re-linked.

Recursive Alternative

A recursive solution compares the two heads and returns the smaller one with its next set to the result of recursively merging the rest. This produces clean code but uses O(m + n) stack space, one frame per node. In an interview, mention this tradeoff to show you have considered both approaches.

Common Pitfalls

1. Forgetting the dummy node: Without it, you need extra conditionals to handle the first comparison. The dummy node is a standard linked-list technique worth memorizing.

2. Not handling null inputs: If either list is null from the start, the while loop body never executes. The tail-attachment step handles this correctly, but forgetting to account for it during a dry run can lead to confusion.

3. Returning dummy instead of dummy.next: The dummy node itself is a placeholder with value 0. Always skip it.

4. Modifying the wrong pointer: Make sure you advance list1 or list2 after attaching the node. A common bug is advancing current before the attachment.

Interview Tips

1. Clarify assumptions: "Are the lists sorted in ascending order? Should I splice existing nodes or create new ones?"

2. Draw it out: Sketch two short lists and trace through two or three iterations. This catches pointer bugs before you write code.

3. Mention the dummy node upfront: Interviewers appreciate when you name the technique. It signals familiarity with linked-list patterns.

4. Discuss the recursive alternative: After presenting the iterative solution, briefly describe the recursive approach and its O(m + n) space cost.

5. Connect to merge sort: If asked a follow-up, explain that this merge operation is the core of merge sort's divide-and-conquer strategy.

Key Takeaways

• A dummy node eliminates special-case logic for initializing the merged list's head. Return dummy.next to skip the placeholder.
• The iterative approach processes each node exactly once for O(m + n) time and reuses existing nodes for O(1) space.
• When one list is exhausted, attach the remaining nodes of the other list in O(1) since they are already sorted and connected.
• The recursive approach is elegant but consumes O(m + n) stack space. Mention this tradeoff in interviews to demonstrate engineering judgment.
• This merge operation is the fundamental building block of merge sort and generalizes to merging K sorted lists using a min-heap.

Practice and Related Problems

Once you are comfortable with this problem, try these related challenges:

• Merge K sorted linked lists (use a min-heap for O(N log K))
• Sort a linked list using merge sort (split with slow/fast pointers, then merge)
• Reverse a linked list (the other essential linked-list pointer pattern)
• Intersection of two linked lists

This problem and many others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed offers at top companies. Consistent practice with problems like this builds the pointer-manipulation instincts that interviewers are looking for.

Solutions in Other Languages

Python

class Solution:
    def merge_two_lists(self, list1, list2):
        dummy = ListNode(0)
        current = dummy

        while list1 and list2:
            if list1.data <= list2.data:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        if list1:
            current.next = list1
        elif list2:
            current.next = list2

        return dummy.next

JavaScript

class Solution {
  mergeTwoLists(list1, list2) {
    let dummy = new ListNode(0);
    let current = dummy;

    while (list1 !== null && list2 !== null) {
      if (list1.data <= list2.data) {
        current.next = list1;
        list1 = list1.next;
      } else {
        current.next = list2;
        list2 = list2.next;
      }
      current = current.next;
    }

    if (list1 !== null) {
      current.next = list1;
    } else {
      current.next = list2;
    }

    return dummy.next;
  }
}

TypeScript

class Solution {
  mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0);
    let current: ListNode = dummy;

    while (list1 !== null && list2 !== null) {
      if (list1.data <= list2.data) {
        current.next = list1;
        list1 = list1.next;
      } else {
        current.next = list2;
        list2 = list2.next;
      }
      current = current.next;
    }

    if (list1 !== null) {
      current.next = list1;
    } else {
      current.next = list2;
    }

    return dummy.next;
  }
}

C++

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *list1, ListNode *list2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->data <= list2->data) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }

        if (list1 != nullptr) {
            tail->next = list1;
        } else {
            tail->next = list2;
        }

        return dummy.next;
    }
};

Go

func (s *Solution) MergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    current := dummy

    for list1 != nil && list2 != nil {
        if list1.Data <= list2.Data {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }
        current = current.Next
    }

    if list1 != nil {
        current.Next = list1
    } else {
        current.Next = list2
    }

    return dummy.Next
}

Scala

The Scala solution uses a recursive approach, which is idiomatic for the language:

class Solution {
  def mergeTwoLists(list1: ListNode, list2: ListNode): ListNode = {
    if (list1 == null) return list2
    if (list2 == null) return list1

    if (list1.data < list2.data) {
      ListNode(list1.data, mergeTwoLists(list1.next, list2))
    } else {
      ListNode(list2.data, mergeTwoLists(list1, list2.next))
    }
  }
}

Kotlin

class Solution {
  fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
    val dummy = ListNode(0)
    var current = dummy
    var node1 = list1
    var node2 = list2

    while (node1 != null && node2 != null) {
      if (node1.data <= node2.data) {
        current.next = node1
        node1 = node1.next
      } else {
        current.next = node2
        node2 = node2.next
      }
      current = current.next!!
    }

    current.next = node1 ?: node2

    return dummy.next
  }
}

Swift

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        let dummy = ListNode(0)
        var current = dummy
        var node1 = list1
        var node2 = list2

        while node1 != nil && node2 != nil {
            if node1!.data <= node2!.data {
                current.next = node1
                node1 = node1!.next
            } else {
                current.next = node2
                node2 = node2!.next
            }
            current = current.next!
        }

        current.next = node1 ?? node2

        return dummy.next
    }
}

Rust

Rust's ownership model makes linked-list manipulation more verbose. The algorithm is the same, but nodes must be explicitly moved via take() and unwrap():

impl Solution {
    pub fn merge_two_lists(
        &self,
        list1: Option<Box<ListNode>>,
        list2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut current = &mut dummy;
        let mut list1 = list1;
        let mut list2 = list2;

        while let (Some(ref n1), Some(ref n2)) = (&list1, &list2) {
            if n1.data <= n2.data {
                let mut node = list1.unwrap();
                list1 = node.next.take();
                node.next = None;
                current.next = Some(node);
            } else {
                let mut node = list2.unwrap();
                list2 = node.next.take();
                node.next = None;
                current.next = Some(node);
            }
            current = current.next.as_mut().unwrap();
        }

        if list1.is_some() {
            current.next = list1;
        } else {
            current.next = list2;
        }

        dummy.next
    }
}

Ruby

class Solution
  def merge_two_lists(list1, list2)
    dummy = ListNode.new(0)
    current = dummy

    while !list1.nil? && !list2.nil?
      if list1.data <= list2.data
        current.next = list1
        list1 = list1.next
      else
        current.next = list2
        list2 = list2.next
      end
      current = current.next
    end

    if !list1.nil?
      current.next = list1
    else
      current.next = list2
    end

    dummy.next
  end
end

C#

public class Solution {
    public ListNode? MergeTwoLists(ListNode? list1, ListNode? list2) {
        var dummy = new ListNode(0);
        ListNode current = dummy;

        while (list1 != null && list2 != null) {
            if (list1.data <= list2.data) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        return dummy.next;
    }
}

Dart

class Solution {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    ListNode dummy = ListNode(0);
    ListNode current = dummy;
    ListNode? node1 = list1;
    ListNode? node2 = list2;

    while (node1 != null && node2 != null) {
      if (node1!.data <= node2!.data) {
        current.next = node1;
        node1 = node1!.next;
      } else {
        current.next = node2;
        node2 = node2!.next;
      }
      current = current.next!;
    }

    current.next = node1 ?? node2;

    return dummy.next;
  }
}

PHP

class Solution {
    public function mergeTwoLists(?ListNode $list1, ?ListNode $list2): ?ListNode {
        $dummy = new ListNode(0);
        $current = $dummy;

        while ($list1 !== null && $list2 !== null) {
            if ($list1->data <= $list2->data) {
                $current->next = $list1;
                $list1 = $list1->next;
            } else {
                $current->next = $list2;
                $list2 = $list2->next;
            }
            $current = $current->next;
        }

        if ($list1 !== null) {
            $current->next = $list1;
        } else {
            $current->next = $list2;
        }

        return $dummy->next;
    }
}