【题目描述】

head=ListNode(None)  current=head复制代码

在一个循环中，当l1和l2都不为空时，从两个链表的头结点开始做比较,在每次循环中，找到l1,l2中较小的那个结点，假如l1.val较小，链接在current之后，即current.next=l1,然后l1和current都依次向后错一位，current到新链表的尾部，l1到下一个比较位置。

current.next=l1current=l1l1=l1.next复制代码

直至l1,l2中有一者或者二者都为空的时候，while循环结束，把二者中不为空的那个结点链接在current之后即可。

if l1:current.next=l1if l2:current.next=l2复制代码

这个解决办法的空间复杂度为O(1)因为只多占用了head和current两个结点空间。时间复杂度为O(m+n)，m,n是两个输入链表的长度，因为只遍历了两个链表一次。 【源代码】

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def mergeTwoLists(self, l1, l2):        """        :type l1: ListNode        :type l2: ListNode        :rtype: ListNode        """        head=ListNode(None)          current=head        while l1 and l2:            if l1.val<=l2.val:                current.next=l1                current=l1                l1=l1.next                  else:                current.next=l2                current=l2                l2=l2.next        if l1:current.next=l1        if l2:current.next=l2        return head.next复制代码