分類：LinkedList
考察知識(shí)點(diǎn)：LinkedList
最優(yōu)解時(shí)間復(fù)雜度：**O(n) **
21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
代碼：
我的解法:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res=ListNode(0)
p1=l1
p2=l2
p=res
while(p1!=None and p2!=None):
if p1.val<=p2.val:
p.next=p1
p1=p1.next
p=p.next
else:
p.next=p2
p2=p2.next
p=p.next
if p1==None:
p.next=p2
elif p2==None:
p.next=p1
return res.next
Beautiful解法:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
res=ListNode(0)
p1=l1
p2=l2
p=res
while(p1 and p2):
if p1.val<=p2.val:
p.next=p1
p1=p1.next
else:
p.next=p2
p2=p2.next
p=p.next
p.next=p2 or p1
return res.next
討論：
1.這道題我的解法是對(duì)的(很好脚粟，雖然是道easy題)
2.但是我的代碼不是很優(yōu)雅不是很beautiful!把代碼改的beautiful后性能提升了很多团南！
我的版本
beautiful版本
