Lintcode 合并两个排序的链表

本文主要是介绍Lintcode 合并两个排序的链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

将两个排序链表合并为一个新的排序链表
样例
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。
递归实现：

"""
Definition of ListNode
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next
"""
class Solution:"""@param two ListNodes@return a ListNode"""def mergeTwoLists(self, l1, l2):# write your code hereif l1 == None:return l2if l2 == None:return l1mergeHead = Noneif l1.val <= l2.val:mergeHead = l1mergeHead.next = self.mergeTwoLists(l1.next,l2)elif l2.val < l1.val:mergeHead = l2mergeHead.next = self.mergeTwoLists(l1,l2.next)return mergeHead

非递归实现：

"""
Definition of ListNode
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next
"""
class Solution:"""@param two ListNodes@return a ListNode"""def mergeTwoLists(self, l1, l2):# write your code hereif l1 == None:return l2if l2 == None:return l1ptr1 = l1ptr2 = l2l = ListNode(0)current = lwhile(ptr1!= None and ptr2 != None):if ptr1.val < ptr2.val:current.next = ptr1ptr1 = ptr1.nextelif ptr1.val > ptr2.val:current.next = ptr2ptr2 = ptr2.nextelse:current.next = ptr1ptr1 = ptr1.nextcurrent = current.nextcurrent.next = ptr2ptr2 = ptr2.nextcurrent = current.nextif ptr1 == None:current.next = ptr2else:current.next = ptr1l = l.nextreturn l

这篇关于Lintcode 合并两个排序的链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---