image.png
解法一、非递归
看到这个问题，想到了最熟悉的归并排序中的归并的过程，其实两个过程是一样的。可以完全类比。
- 首先判断是否为空链表，如果一方为空链表，则直接返回另外的头指针即可。
- 然后合并两个链表，将两个链表的头部小的那个，作为p指针的next, 直到有一方空了，直接将另一方接到后面就好了。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
if pHead1.val <= pHead2.val:
head = pHead1
pHead1 = pHead1.next
else:
head = pHead2
pHead2 = pHead2.next
p = head
while pHead1 and pHead2:
if pHead1.val <= pHead2.val:
p.next = pHead1
pHead1 = pHead1.next
p = p.next
else:
p.next = pHead2
pHead2 = pHead2.next
p = p.next
if pHead1 == None:
p.next = pHead2
if pHead2 == None:
p.next = pHead1
return head
解法二：递归的方法
image.png
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
if pHead1 == None:
return pHead2
elif pHead2 == None:
return pHead1
pMergedHead = None
if pHead1.val < pHead2.val:
pMergedHead = pHead1
pMergedHead.next = self.Merge(pHead1.next,pHead2)
else:
pMergedHead = pHead2
pMergedHead.next = self.Merge(pHead1, pHead2.next)
return pMergedHead
