难度：容易
1. Description
165. 合并两个排序链表
2. Solution
- python
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param l1: ListNode l1 is the head of the linked list
@param l2: ListNode l2 is the head of the linked list
@return: ListNode head of linked list
"""
def mergeTwoLists(self, l1, l2):
# write your code here
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val>l2.val:
l1,l2 = l2,l1
node = l1
cur1 = l1.next
cur2 = l2
while True:
if cur1.val<cur2.val:
node.next = cur1
cur1 = cur1.next
node = node.next
if cur1 is None:
node.next = cur2
break
else:
node.next = cur2
cur2 = cur2.next
node = node.next
if cur2 is None:
node.next = cur1
break
return l1
下面的方法比较麻烦，是把l2插入到l1中。
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param l1: ListNode l1 is the head of the linked list
@param l2: ListNode l2 is the head of the linked list
@return: ListNode head of linked list
"""
def mergeTwoLists(self, l1, l2):
# write your code here
if l1 is None:
return l2
if l2 is None:
return l1
if l1.val>l2.val:
l1,l2 = l2,l1
cur1 = l1
cur2 = l2
while cur1.next is not None and cur2 is not None:
pre1=None
while cur1 is not None and cur1.val<=cur2.val:
pre1 = cur1
cur1 = cur1.next
if cur1 is None:
cur1 = pre1
break
tmp = pre1.next
pre1.next = cur2
cur2 = cur2.next
pre1.next.next=tmp
cur1 = pre1.next
if cur1.next is None:
cur1.next = cur2
return l1
else:
return l1
