# Merge Two Sorted Lists

Published: Sep 22, 2022

## Introduction

This is a basic linked list problem. When it is a linked list, we should always consider adding a dummy node at the head. This makes easy to handle the given linked list’s head node.

## Problem Description

You are given the heads of two sorted linked lists `list1` and `list2`. Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

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.

https://leetcode.com/problems/merge-two-sorted-lists/

## Examples

``````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 = 
Output: 

``````

## Analysis

Create a dummy node first since we don’t know which one will come first. Also, use a current pointer to go forward. While both list1 and list2 have nodes, add one of those with grater value to current’s next. If one of list1 or list2 comes to end, add entire rest to current’s next. In the end, return dummy node’s next which points the head of list1 or list2.

## Solution

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class MergeTwoSortedLists:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
while list1 and list2:
if list1.val <= list2.val:
cur.next = list1
list1 = list1.next
else:
cur.next = list2
list2 = list2.next
cur = cur.next
cur.next = list1 or list2
return dummy.next
``````

## Complexities

• Time: `O(m + n)` – m,n: length of list1, list2 respectively
• Space: `O(1)`