Coding problem · Easy · Linked List

Merge Two Sorted Lists

Easy Algorithms & data structures Most askedSeen at Amazon, Microsoft, Apple, Adobe

Given the heads of two sorted linked lists list1 and list2, merge them into one sorted list by splicing together their nodes, and return its head.

Example 1

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

Hints

Hint 1

A dummy head node removes the special case of choosing the first node.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n + m) · Space O(1)

Attach the smaller head to a tail pointer that starts at a dummy node, advance that list, and repeat. When one list runs out, attach the remainder of the other in one step.

Reference solution

function mergeTwoLists(a, b) {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a ?? b;
  return dummy.next;
}

function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next!;
  }
  tail.next = a ?? b;
  return dummy.next;
}

def merge_two_lists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = tail = ListNode()
    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
    return dummy.next

<?php

function 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 ?? $list2;
    return $dummy->next;
}

class Solution {
    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }
}

Follow-up questions

Merge k sorted lists (min-heap of heads, O(N log k)).

Reverse Linked List · Easy
Linked List Cycle · Easy
Remove Nth Node From End of List · Medium