21. 合并两个有序链表
题目简述一下，就是给定两个升序有序链表，然后合并它们。
昨天看到这个题目，我的大脑一片空白，其实这个题目没什么难的，就是单纯地考察对一个数据结构链表的掌握程度，单链表。
太久没有写了，真的写不出，我就看了答案，意思我是完全知道的，但是就是写不出：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# 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: ListNode, l2: ListNode) -> ListNode:
result = ListNode(-1)
point = result
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l2.next
point = point.next
point.next = l1 if l1 is not None else l2
return result.next
以上是看完答案默写的，首先是声明两个新的指针，一个指向最后结果的链表头，另一个是用作游标，然后就是迭代，注意看里面 next 也是一个指针，也利用到了。
这个题目还可以写出其递归算法，其具有的递归结构是这样的，在给定的两个链表里，找到一个最小的节点后，去掉这个节点，剩下的问题跟原理的问题是一致的，递归调用原来的解法就可以了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# 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: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
result = ListNode(-1)
if l1.val <= l2.val:
result.next = l1
l1.next = self.mergeTwoLists(l1.next, l2)
else:
result.next = l2
l2.next = self.mergeTwoLists(l1, l2.next)
return result.next
先找到最小的节点，然后，把剩下的递归解决。写完看了下，发现 result 是完全多余的，去掉也可以。就跟官方给的题解一样了。
知识点：
- 链表的数据结构的特点；
- Python 里一个类变量是引用类型的；
- 可以用 is None 和 is not None 这样的运算来判空。
