21. 合并两个有序链表

语言: CN / TW / HK

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

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

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

# 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 也是一个指针,也利用到了。

这个题目还可以写出其递归算法,其具有的递归结构是这样的,在给定的两个链表里,找到一个最小的节点后,去掉这个节点,剩下的问题跟原理的问题是一致的,递归调用原来的解法就可以了。

# 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 这样的运算来判空。
分享到: