Merge Two Sorted Lists: Dummy node Pattern

Learning Outcome

After this lesson, you should be able to merge two sorted linked lists by attaching the smaller current node to a result list.

Problem Statement

Given the heads of two sorted linked lists, merge them into one sorted linked list and return its head.

Brute Force Approach

Copy all values into an array, sort the array, and build a new linked list.

This works, but it wastes the fact that both lists are already sorted and uses extra space.

Optimized Approach

Use a dummy node before the answer and a tail pointer. Compare the current nodes of both lists, attach the smaller node to tail.next, then move that list forward.

When one list finishes, attach the remaining part of the other list directly.

Exact Pseudocode

dummy = new node
tail = dummy
while list1 is not null and list2 is not null:
  if list1.val <= list2.val:
    tail.next = list1
    list1 = list1.next
  else:
    tail.next = list2
    list2 = list2.next
  tail = tail.next
tail.next = list1 if list1 is not null else list2
return dummy.next
  

Reference Code

class Solution:
    def mergeTwoLists(self, list1, list2):
        dummy = ListNode(0)
        tail = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                tail.next = list1
                list1 = list1.next
            else:
                tail.next = list2
                list2 = list2.next
            tail = tail.next

        tail.next = list1 if list1 else list2
        return dummy.next
  

Sample Dry Run

Complexity

Edge Cases

• One list is empty.
• Both lists are empty.
• Duplicate values appear in both lists.

Interview Checklist

• Use a dummy node to avoid special-casing the head.
• Move tail after every attachment.
• Attach the remaining list at the end.

FAQs