LeetCode21-合并两个有序链表

昨天晚上终于是把我铭锅从澳洲带过来的巧克力

给qio完了

真的是满满的卡路里啊！

吃的时候是真的爽到爆

一吃完

立马就陷入深深地自责当中

于是

晚上急忙去健身房跑了9km

今天的热量

应该是消耗完了吧！

还有，最近突然get到日本女明星的颜值

今天安利的是新垣结衣，满满的初恋印象啊！

---

21-合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

这一题我能想到还不错的有两种方法，第一种方法是：新建一链表，然后依次遍历给定的两个有序链表，一一比较，每次将比较所得的最小值对应的节点插入到新建的链表后面（这个建表方法属于尾插法），两个有序链表长度可能不一样，但只要有一方先行遍历完了，直接将没遍历完的链表插入到新建链表的后面即可。这种方法执行效率还是挺不错的，我测的几次都至少在80%以上。

第二种方法其实之前也提到过，我们可以先遍历完两个有序链表，依次将对应得值存放到设定的数组当中，然后直接用sort()方法排序，最后新建一链表，将排序好的数组当中的值依次插入到链表后面即可，这个方法我这里就不写了，感兴趣的朋友可以自行复现，不难的！

方法一代码如下：

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l1_copy = l1
        l2_copy = l2
        combination = ListNode(0)
        com_copy = combination
        while l1_copy and l2_copy:
            if l1_copy.val <= l2_copy.val:
                com_copy.next = l1_copy
                l1_copy = l1_copy.next
                com_copy = com_copy.next
            else:
                com_copy.next = l2_copy
                l2_copy = l2_copy.next
                com_copy = com_copy.next
        if l1_copy and not l2_copy:
            com_copy.next = l1_copy
        elif not l1_copy and l2_copy:
            com_copy.next = l2_copy
        return combination.next


if __name__ == '__main__':
    l1 = ListNode(0)
    l1_copy = l1
    l2 = ListNode(0)
    l2_copy = l2
    l1_num = [1, 2, 4]
    l2_num = [3, 6, 9]
    for num in l1_num:
        l1_copy.next = ListNode(num)
        l1_copy = l1_copy.next
    for num in l2_num:
        l2_copy.next = ListNode(num)
        l2_copy = l2_copy.next
    result = Solution().mergeTwoLists(l1.next, l2.next)
    while result:
        print(result.val)
        result = result.next

执行效率如下：