将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2...
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
分析：记得在严蔚敏《数据结构c语言版》中做过类似题目，思路很简单，新建一个头结点，从两表第一个结点开始进行比较，当两个链表L1和Lb2均未到达表尾结点时，则依次摘取较小元素重新链接在新表的后面。若有一表达到尾结点，因为输入链表有序，所以直接将另外一表插入到新表末尾即可。另外注意代码的鲁棒性，要考虑到空指针的输入。Python实现如下：
class Solution:
def mergeTwoLists(self, l1, l2):
\"\"\"
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
\"\"\"
#头结点置空，若有空表输入，返回的也为空
head=ListNode(None)
temp=head
while l1 and l2:
if l1.val<=l2.val:
temp.next=l1
l1=l1.next
else:
temp.next=l2
l2=l2.next
temp=temp.next
temp.next=l1 if l1 else l2
#注意这里是返回头结点而不是temp指针
return head.next
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
