---
title: '21. Merge Two Sorted Lists'
description: You are given the heads of two sorted linked lists list1 and list2
sidebar:
  label: 'Merge Two Sorted Lists'
  badge: 'Easy'
---

Linked 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: `[]`

### 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.

## Approach

```mermaid
flowchart TD
  S(["mergeTwoLists(list1, list2)"]) --> G1{"list1 empty?"}
  G1 -- yes --> X1(["return list2"])
  G1 -- no --> G2{"list2 empty?"}
  G2 -- yes --> X2(["return list1"])
  G2 -- no --> H["head = the smaller first node; advance that list"]
  H --> C["current = head"]
  C --> W{"list1 and list2 both non-empty?"}
  W -- yes --> P["current.next = the smaller node; advance that list; current = current.next"]
  P --> W
  W -- no --> T["current.next = list1 or list2 — append the leftover tail"]
  T --> E(["return head"])
```

## Solution

```py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: Optional[ListNode], list2: Optional[ListNode]
    ) -> Optional[ListNode]:

        if not list1:
            return list2
        if not list2:
            return list1

        if list1.val < list2.val:
            head = list1
            list1 = list1.next
        else:
            head = list2
            list2 = list2.next

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

        current.next = list1 or list2
        return head
```

## Explanation

[Merge Two Sorted Lists - Leetcode 21 - Python](https://www.youtube.com/watch?v=XIdigk956u0)