# LeetCode: 21. Merge Two Sorted Lists

## 题目¶

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example 1:

```Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
```

Example 2:

```Input: l1 = [], l2 = []
Output: []
```

Example 3:

```Input: l1 = [], l2 = [0]
Output: [0]
```

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

## 解法¶

### 同时遍历两个链表，比较各个节点的值构建新的有序链表¶

• 定义一个新的链表 dummy 然后通过两个指针同时遍历两个链表
• 如果 A 链表当前节点值小于或等于 B 链表当前节点的值，则将新链表的 tail 指向 A 链表当前节点， A 的遍历指针移到下一个节点，B 保持不变
• 如果 A 链表当前节点值大于 B 链表当前节点的值，则将新链表的 tail 指向 B 链表当前节点， B 的遍历指针移到下一个节点，A 保持不变
• 如果 A 的遍历指针到了链表最后位置无法再移动了，直接把新链表的 tail 指向 B 链表当前节点（因为 B 是个有序链表所以不需要再对 B 继续处理）
• 如果 B 的遍历指针到了链表最后位置无法再移动了，直接把新链表的 tail 指向 A 链表当前节点（因为 B 是个有序链表所以不需要再对 A 继续处理）

```# 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, l1, l2):
if l1 is None:
return l2
if l2 is None:
return l1

dummy = ListNode()
tail = dummy

while l1 is not None and l2 is not None:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next

tail = tail.next
if l1 is None:
tail.next = l2
if l2 is None:
tail.next = l1

return dummy.next
```