2019-06-10剑指合并排序链表

1.错在大小符号
2.哑结点的妙用

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        dead=ListNode(None) #想破脑袋第一个节点怎么办，哑结点真的妙
        end=dead
        while pHead1!=None and pHead2!=None:
            if pHead1.val<=pHead2.val:
                end.next=pHead1
                pHead1=pHead1.next
            else:
                end.next=pHead2
                pHead2=pHead2.next
            end=end.next
            end.next=None
        if pHead1!=None:
            end.next=pHead1
        if pHead2!=None:
            end.next=pHead2
        return dead.next

python 的魔法方法+去掉尾部不会造成死循环

class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        dead=ListNode(None) #想破脑袋第一个节点怎么办，哑结点真的妙
        end=dead
        while pHead1!=None and pHead2!=None:
            if pHead1.val<=pHead2.val:
                end.next=pHead1
                pHead1=pHead1.next
            else:
                end.next=pHead2
                pHead2=pHead2.next
            end=end.next
        end.next=pHead1 or pHead2
        return dead.next

递归解法更简单

class Solution:
    # 返回合并后列表
    def Merge(self, l1, l2):
        # write code here
        if not l1 or not l2:
            return l1 or l2
        if l1.val<=l2.val:
            l1.next=self.Merge(l1.next,l2)
            return l1
        else:
            l2.next=self.Merge(l1,l2.next)
            return l2