0.引言

写在前面的话：这道题按计划本来不是我的，但是呢，这个题涉及到的链表知识是我比较欠缺的，所以在跟梅子同学友好协商之后，我也可以更新这道题了，哈哈哈。

1.题目

原题：

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

例子：

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

2.解析

2.1 基本思路

这道题本质是数据结构的题，考察的是用python实现单链表，进一步的操作是对单链表进行排序。
在做这个题之前，我们可以先考虑一下，对普通的列表怎么进行排序，最简单粗暴的想法是将两个列表extend到一起，然后直接用sort函数进行排序，但是这么做显然是浪费时间的。我们可以设置两个指针，分别对两个列表进行遍历迭代，小的那个列表指标+1，直至某个列表为空。
有了前边列表这个排序经验我们就可以对链表合并进行思考，首先最简单的是把链表合到一起，然后利用排序算法进行排序，这无疑增加算法复杂度，我们要放弃。我们可以设置一个新的链表，然后依次去两个链表中的两个节点进行连接，最后得到合并后的链表。

2.2 用到的知识点

• 链表初始化，定义一个head，可以赋值为0
• 链表更新，将初始化的head赋值给newl，newl可以跟随head进行同样的变化操作，并且保持了head得链条结构，我们可以对head进行next操作，用newl保存
• 链表输出打印，用while语句，内部嵌套打印和next操作
• list转列表可以事先定义好函数，循环list拼接乘最后的链表

3.python代码

3.1 两个普通排序列表的合并

class Solution()
    def merge2lists(self, l1, l2):
        l1len = len(l1)
        l2len = len(l2)
        newl = []
        p, q = 0, 0
        while p < l1len or q < l2len:
            print(p, q)
            if p >= l1len:
                newl.extend(l2[q:])
                break
            if q >= l2len:
                newl.extend(l1[p:])
                break
            if l1[p] < l2[q]:
                newl.append(l1[p])
                p += 1
            else:
                newl.append(l2[q])
                q += 1
        return newl

3.2 两个有序链表的合并

class Solution:
    def mergeTwoLists(self, list1, list2):
        head = ListNode(0)
        newl = head
        while list1 is not None or list2 is not None:#根据链表的特点
            if list1 is None:
                head.next = list2
                break
            if list2 is None:
                head.next = list1
                break
            if list1.value < list2.value:
                head.next = list1
                list1 = list1.next
            else:
                head.next = list2
                list2 = list2.next
            head = head.next
        return newl.next