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

# -*- coding: utf-8 -*-# @Time : 2019-04-24 10:17# @Author : Jayce Wong# @ProjectName : job# @FileName : mergeSortedLinkedList.py# @Blog : https://blog.51cto.com/jayce1111# @Github : https://github.com/SysuJayceclass ListNode: def __init__(self, x): self.val = x self.next = Noneclass Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # 如果任何一个链表为空，那么返回另一个链表 if not pHead1: return pHead2 if not pHead2: return pHead1 # 选择两个头节点中值最小的那个作为新的头节点，然后新的头节点的下一个节点就可以递归下去 if pHead1.val < pHead2.val: head = pHead1 head.next = self.Merge(pHead1.next, pHead2) else: head = pHead2 head.next = self.Merge(pHead1, pHead2.next) return head def Merge2(self, pHead1, pHead2): # 也可以不用递归的方法，使用循环的方法来归并链表 # 借助两个辅助节点，其中begin用于定位返回链表的头节点，pre用于定位返回链表的当前节点 begin = pre = ListNode(0) while pHead1 and pHead2: if pHead1.val < pHead2.val: pre.next = pHead1 pre = pre.next pHead1 = pHead1.next else: pre.next = pHead2 pre = pre.next pHead2 = pHead2.next # 注意处理两个链表长度不一致的情况 if not pHead1: pre.next = pHead2 if not pHead2: pre.next = pHead1 return begin.nextdef main(): p1 = ListNode(1) p1.next = ListNode(3) p1.next.next = ListNode(5) p2 = ListNode(2) p2.next = ListNode(4) p2.next.next = ListNode(6) p = Solution().Merge(p1, p2) while p: print(p.val) p = p.nextif __name__ == '__main__': main()