Description

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

Solutions

可以用迭代的方法搞定:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        pRes = None
        pNode = None
        
        while pHead1 and pHead2:
            pNext = None
            if pHead1.val <= pHead2.val:
                pNext = pHead1
                pHead1 = pHead1.next
            else:
                pNext = pHead2
                pHead2 = pHead2.next
            
            if pNode is None or pRes is None:
                pRes = pNext
                pNode = pNext
                continue
            
            pNode.next = pNext
            pNode = pNode.next
        
        if pHead1 or pHead2:
            if pNode is not None:
                pNode.next = pHead1 or pHead2
            else:
                pRes = pHead1 or pHead2
        
        return pRes

当然,利用迭代方式很明显不是很优雅,可以尝试使用递归的方式实现:

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        if pHead1 is None :
            return pHead2
        elif pHead2 is None:
            return pHead1
        pNode = None
        if pHead1.val <= pHead2.val:
            pNode = pHead1
            pNode.next = self.Merge(pHead1.next, pHead2)
        else:
            pNode = pHead2
            pNode.next = self.Merge(pHead1, pHead2.next)
        return pNode

要是要首先搞清楚递归的过程再去写代码,别写代码以猜的心态,交给上帝去调试?

References

  1. 017. 合并两个排序的链表