Merge Two Sorted Lists

easy Linked List

You are given the heads of two sorted linked lists, list1 and list2. Merge them into a single sorted linked list by splicing together the nodes from both lists. Return the head of the merged list. The merged list should contain all nodes from both input lists in non-decreasing order.

Example

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

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

Both lists are already sorted individually. The merged result contains all elements from both lists arranged in non-decreasing order.

Create a dummy head node so you don't need special logic for the first element. Compare the heads of both lists and attach the smaller one to your result. Keep going until one list is exhausted, then attach the remainder of the other list directly.

Why this works

Both input lists are already sorted. At each step, you just compare the two front elements and take the smaller one. This is the same idea as the “merge” step in merge sort. By always choosing the smallest available node, the result list stays sorted.

Step by step

Create a dummy node — this placeholder lets you build the result without worrying about initializing the head separately.
Compare and attach — at each step, compare list1.val and list2.val, attach the smaller node to curr.next, and advance that list’s pointer.
Advance the tail — move curr forward so the next node gets appended at the end.
Attach the remainder — when one list runs out, the other is already sorted, so just link it directly.

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

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);  // avoids special-casing the first node
        ListNode curr = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {  // pick the smaller head
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        curr.next = (list1 != null) ? list1 : list2;  // attach whichever list remains
        return dummy.next;
    }
}

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);  // avoids special-casing the first node
        ListNode* curr = &dummy;
        while (list1 && list2) {
            if (list1->val <= list2->val) {  // pick the smaller head
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }
        curr->next = list1 ? list1 : list2;  // attach whichever list remains
        return dummy.next;
    }
};

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)  # avoids special-casing the first node
    curr = dummy
    while list1 and list2:
        if list1.val <= list2.val:  # pick the smaller head
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    curr.next = list1 if list1 else list2  # attach whichever list remains
    return dummy.next