006Merge Two Sorted Lists

Problem

给定两个已经按升序排列的链表 list1 和 list2。

请将它们合并成一个新的升序链表，并返回合并后链表的头节点。

新链表应该由原来两个链表中的节点拼接而成。

Examples

示例 1

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

示例 2

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

示例 3

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

Constraints

• 两个链表中的节点数范围都是 $[0, 50]$
• $-100 \leq$ Node.val $\leq 100$
• list1 和 list2 都按非递减顺序排列