Easy 21 – 合并两个有序链表

给定两个有序链表（linked list），要求返回一个有序链表。

我第一反应是把所有的value取出来，然后直接sorted，这样问题就解决了。转念一想，搞两个循环再加一个本身就很需要时间的方法，这个办法怎么听都很蠢，而且就算把两个链表里的元素都存到了一个list里，我还要再把sorted list做成链表，这样听起来这个办法更蠢了。（但能解决问题对不对？工程思维突然浮现了！）

还是直接看答案吧家人们，看了看答案就知道，这绝对不是我这种半吊子都达不到的人能想出来的。

第一种解法是用了递归的思想，是给了代码我能看懂，但让我自己写我绝对写不出来的程度。

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

leetcode的题解对递归的思想进行了解释，其实有点像高中数学刚学函数那会儿做的题目，一步步的往下推，直到有已知的函数值为止。

已知：f(x) = f (x-1) + 2, f(0) = 0，求f(5)

一边写一边感觉DNA动了……要做这道题的话，就是一路写下去，然后发现f(1)的值可求（是2），然后一路再加上来，发现f(5)的值是10.

当然了，道理是简单的，例题也总是比较简洁易懂，但是实际情况肯定会比这种简单的累加更抽象更难懂。合并列表还是easy，但是已经有点难以理解了。（反正对我来说已经猪脑过载。

第二个是用迭代的想法，这个和我在最开始提出来的想法差不多，同样借助另外一个空的链表进行数据的存储。等到有一个链表空了就把next指向另外一个list接下来的值就可以了。

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        prehead = ListNode(-1)

        prev = prehead
        while l1 and l2:
            if l1.val <= l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next            
            prev = prev.next

        # 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 if l1 is not None else l2

        return prehead.next

这个没啥好说的，那这个题目就到这儿吧……

下次要是再遇到类似的，我肯定自己先试试！