easyLinked Lists

Merge Two Sorted Lists

## Problem

You are given the heads of two sorted linked lists `list1` and `list2`.

Merge the two lists into one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

> **Note:** For this problem, represent each list as a Python list. Return the merged sorted list.

Examples

Input

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

Output

[1,1,2,3,4,4]

Merged in sorted order.

Input

list1 = [], list2 = []

Output

[]

Both lists empty.

Input

list1 = [], list2 = [0]

Output

[0]

First list empty.

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.

Python