36. Merge Two Sorted Lists

EasyLinked ListsAlso on LeetCode ↗

Merge two sorted linked lists into one sorted list by splicing the existing nodes together, and return its head.

Example 1

Input: list1 = [1,3,5], list2 = [2,4,6]

Output: [1,2,3,4,5,6]

Example 2

Input: list1 = [], list2 = []

Output: []

Hint 1

A dummy head node removes the “is the result empty?” special case.

Linked List

Reference solution for Iterative with dummy head (time O(n + m), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode()        # dummy head avoids special cases
        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 or list2       # attach what is left
        return dummy.next

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(), tail = dummy;
        while (list1 != null && list2 != 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 != null) ? list1 : list2;
        return dummy.next;
    }
}

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy, *tail = &dummy;
        while (list1 && 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 ? list1 : list2;
        return dummy.next;
    }
};

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode();
  let tail = dummy;
  while (list1 && 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 || list2;
  return dummy.next;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

36. Merge Two Sorted Lists

Example 1

Example 2

Approach 1: Iterative with dummy head ✅