LeetCode21_合并两个有序链表

2019-09-23

用python语言解答LeetCode的21题

碎碎念（不用看！下一节开始才是重点~~~）

似乎以前做过合并有序数组的题，不对，是绝对做过，之前c语言加强课（其实就是算法课）的题库里面有这道题，记得当时还搞懂了，不过现在又忘记了，果然知识还是得反复学习才行啊。
感觉这个题在考察链表的插入诶，题目要求是将两个有序链表合并成一个新的有序链表并返回。而且新链表是通过拼接给定的两个链表的所有节点组成的，意思也就是不要创建新的节点，而是拼接原有的结点。说了这么多，脑袋里面还是木有解题思路，其实有一个，但是感觉好复杂。。。
把一个链表固定着，然后遍历另一个链表，根据元素大小把这个链表的结点插入那个固定的链表里面。实现的话。。。不会。。。我知道这题很简单，，，可是我就是不会。。。好了，没啥想说的了。。。我去看网上各路大神的思路了。

合并两个有序链表和合并两个有序数组

方法一：非递归

新建一个带有哨兵结点的链表，依次比较两个有序链表的结点值，将较小值的结点插入到新链表后面。直到其中一个比较完毕，将另一个链表剩余的结点全部放到新链表最后面即可。最后，可以删除哨兵结点，或者直接返回哨兵结点后第一个结点指针。

方法二：递归

avatar

其实这个思路我也没太理顺，但是递归的思想是大概理顺了的，这里先讲一个经典的例子，帮助理解递归，至于这道题的递归思路，后面多做点题估计就可以过来讲这道题的思路了
f(n) = 1+2+3+…+n

这个代码很好写：


    def f(n)
        if n == 0
            return 0
        else
            return n + f(n - 1)

假设我们要求f(3),那么它的过程就是这样子的：

avatar

最后一级一级的返回回去，就可以求出f(3)的值啦
写递归有两个很重要的元素：
其一是出口，出口一定要有啊，否则会导致栈溢出的
其二就是递归体啦。

合并两个有序链表用递归解的大致思想就是：

每次递归的时候都能保证子链的头结点是剩余所有元素中最小的那个。

因为链表是有序的，所以只要链表一的头结点小于链表二的头结点，那么链表一的头结点就一定是当前元素中最小的那个元素了，那么每一个元素的后续节点都是剩余所有元素中最小的那个，最后自然排出来就是一个有序的链表了。

方法二的代码：


    # Definition for singly-linked list.
    # class ListNode
    #     def __init__(self, x)
    #         self.val = x
    #         self.next = None

    class Solution
        def mergeTwoLists(self, l1 ListNode, l2 ListNode) - ListNode
            if l1 is None
                return l2
            if l2 is None
                return l1
            elif l1.val  l2.val
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2

方法二的运行结果：

avatar

Reference：

1.httpswww.cnblogs.comyqpyp9545645.html
2.归并排序和本题解题思路进行对比httpsblog.csdn.netJXH_123articledetails38371523
3.对递归的理解httpswww.bilibili.comvideoav61692380from=search&seid=8154685392981106848