Problem statement

You are given the heads of two singly linked lists, list1 and list2, each sorted in non-decreasing order.

Join them into one sorted list by relinking the nodes of the two lists (no new values are created), and return the head of the merged list.

Example 1

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

Example 2

Input: list1 = [], list2 = []
Output: []
Explanation: Two empty lists merge into an empty list.

Example 3

Input: list1 = [], list2 = [0]
Output: [0]

Constraints

• The number of nodes in both lists is in the range [0, 50]
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order

Hints for Merge Two Sorted Lists

1. Hint 1

   The smallest value of the merged list is the smaller of the two heads.

2. Hint 2

   Repeatedly take the smaller head, append it to the result, and advance that list.

3. Hint 3

   A dummy node in front of the result removes the special case for the first node; when one list runs out, attach the rest of the other in one step.

How to solve Merge Two Sorted Lists

The merged list is built front to back by always taking the smaller of the two current heads — the merge step of merge sort, done on links instead of array slots.

Approach

1. Create a dummy node and a tail pointer at it.
2. While both lists are non-empty, compare their heads; link the smaller one after tail, advance that list and move tail forward.
3. When one list is exhausted, link the remainder of the other after tail — it is already sorted.
4. Return dummy.next.

Why it works

At every step the chosen node is no larger than any node not yet taken, because both lists are sorted and we compare their smallest remaining elements. So the output is sorted and contains every node exactly once.

Complexity

• Time — O(n + m)
• Space — O(1) — only links change

Pitfalls

• Either input may be empty; the dummy node handles both without special code.
• Take from list1 on ties (<=) — any choice is sorted, but be consistent.
• Do not forget the leftover tail after the loop.

Reference solution

Python

from typing import Optional

def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    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

Java

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0), 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;
}

C++

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0);
    ListNode* 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;
}

JavaScript

var mergeTwoLists = function(list1, list2) {
    var dummy = new ListNode(0), 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;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More two pointers problems

• Palindrome Linked List Easy
• Reverse Linked List Easy
• Remove Linked List Elements Easy
• Check if Two Trees are Isomorphic Easy
• Transform to Sum Tree Easy
• Power of Four Easy