分类刷题：链表的增加

JZ25 合并两个排序的链表

输入：{1,3,5},{2,4,6}

输出：{1,2,3,4,5,6}

输入：{-1,2,4},{1,3,4}

输出：{-1,1,2,3,4,4}

解法1： 转成list来做，好处在于可以直接用sort

    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # write code here
        if pHead1 is None and pHead2 is None:
            return None
        elif pHead1 is not None and pHead2 is None:
            return pHead1
        elif pHead2 is not None and pHead1 is None:
            return pHead2
        l = []
        while pHead1 is not None:
            l.append(pHead1.val)
            pHead1 = pHead1.next
        while pHead2 is not None:
            l.append(pHead2.val)
            pHead2 = pHead2.next

        l = sorted(l)
        new_l = ListNode(l[0])
        head_l = new_l
        for i in range(1,len(l)):
            new_l.next = ListNode(l[i])
            new_l = new_l.next
        #new_l.next = None
        return head_l

注意：

1. 链表和列表之间是可以用.val来连接的，换句话说链表中.val可以作为元素append到列表之中
2. 注意把list转化成listNode的方法要先设立一个listNode[0]的表头，然后用new_l.next = ListNode(l[i])，注意不是直接=l[i]要用一个listnode给框起来

解法2：双指针

    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        dummy = cur = ListNode(0)
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            cur = cur.next
        if pHead1:
            cur.next = pHead1
        else:
            cur.next = pHead2
        return dummy.next

注意：

1. 一定要记得在第十行这里需要往后面跳一个，没跳的话输出是一个值，而且并非哑节点的问题。

2. 11-14行可以写成：cur.next = pHead1 or pHead2