21. 合并两个有序链表

发表于 分类于 阅读次数： 本文字数： 345 阅读时长 ≈ 1 分钟

题目简述一下，就是给定两个升序有序链表，然后合并它们。

昨天看到这个题目，我的大脑一片空白，其实这个题目没什么难的，就是单纯地考察对一个数据结构链表的掌握程度，单链表。

太久没有写了，真的写不出，我就看了答案，意思我是完全知道的，但是就是写不出：

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 是完全多余的，去掉也可以。就跟官方给的题解一样了。

知识点：

  1. 链表的数据结构的特点；
  2. Python 里一个类变量是引用类型的；
  3. 可以用 is None 和 is not None 这样的运算来判空。