LeetCode高频100题刷题记录之——升序链表合并

1 思路分析

这题算是我在刷题的时候碰到的第一个大坑，坑的不是题目本身，而是链表结构在python中的结构，在python中，变量分为可变变量与不可变变量，比如这题的链表，就是一个不可变变量，给两个符号赋相同的链表后，修改其中的一个，另一个会跟着改变，但又不是整个变量都改变了，而只是对应结点地址处产生了变化，也因此最终可以实现链表的功能。

2 迭代法求解

这个代码的思想是创建一个新的链表，来比较 l 1 l1 l1与 l 2 l2 l2中每个数的大小，最终将两个链表中的所有数字按从小到大的规律排序送入 l 3 l3 l3中。这里定义了一个$l3 _ ， 其 初 始 值 与 ，其初始值与 ，其初始值与l3 一 样 ， 但 在 后 续 每 次 迭 代 时 ， 将 一样，但在后续每次迭代时，将 一样，但在后续每次迭代时，将l3 _ .next 中 的 值 使 用 中的值使用 中的值使用l1 与 与 与l2 中 最 小 的 那 个 替 换 ， 这 里 ， 改 变 了 中最小的那个替换，这里，改变了 中最小的那个替换，这里，改变了l3 _ .next 指 向 的 地 址 的 数 值 ， 因 此 指向的地址的数值，因此 指向的地址的数值，因此l3$也被相应的改变了，也因此才能实现C语言中类似指针的效果。

这题真的是在实现上折磨了我很久，因为对python语言的不够了解，导致思路想清楚了但是一直做不出来，因此最后的代码极大地参考了官方题解，但我个人的做题思路与官方题解是比较一致的，但是实现不如官方题解整洁，因此下面的代码与官方题解高度雷同，但好歹是学会了，但是链表的结构还应该好好地学习。

# 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 l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            l3 = ListNode()
            l3_ = l3

            while l1 and l2:
                if l1.val <= l2.val:
                    l3_.next = l1
                    l1 = l1.next
                else:
                    l3_.next = l2
                    l2 = l2.next
                l3_ = l3_.next
            
            l3_.next = l1 if l1 else l2  # 注意，是给next赋值，而不是给当前的node赋值
            return l3.next  # 因为是给next赋值，因此最后l3的第一个元素是无关紧要的

           

3 递归法实现

使用递归其实不如使用迭代解这一题的效率高，但是学习递归的思想是很有必要的。

之前从没使用过递归解决这个问题，因此这一题是写法是参考了官方的题解以后，自己写了一遍，过了三天再重新自己思考实现的。思路在于，判断 l 1 l1 l1与 l 2 l2 l2是不是有空的，有就返回另一个，这一点比较简单，略去不说；递归部分，首先判断一下两个链表当前节点的值的大小，把小的那一个作为初始节点，然后对下一个节点继续这样的比较，直到指向最后一个节点，也就是None，每次迭代，链表都会指向i西安一个节点，因此可以遍历所有的节点，再一步步返回比较后的结果，最终得到排序好的链表。

# 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 l1 is None:
            return l2
        elif l2 is None:
            return l1
        else:
            if l1.val <= l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2