美文网首页
合并两个排序链表

合并两个排序链表

作者: 与蟒唯舞 | 来源:发表于2018-01-25 16:39 被阅读184次
LintCode 165 题
将两个排序链表合并为一个新的排序链表

给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15->null

使用 python 语言实现:

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


class Solution:
    def merge_two_lists(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = None
        current = None
        while l1 is not None and l2 is not None:
            if l1.val < l2.val:
                if head is None:
                    head = current = l1
                else:
                    current.next = l1
                    current = l1
                l1 = l1.next
            else:
                if head is None:
                    head = current = l2
                else:
                    current.next = l2
                    current = l2
                l2 = l2.next
        if l1 is None:
            current.next = l2
        else:
            current.next = l1
        return head         
            
    """
    递归
    @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 merge_two_lists_recursive(self, l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1.val < l2.val:
            head = l1
            head.next = self.merge_two_lists_recursive(l1.next, l2)
        else:
            head = l2
            head.next = self.merge_two_lists_recursive(l1, l2.next)
        return head   

# 测试代码1,建立链表:1->3->8->11->15->None
l1_0 = ListNode(1)
l1_1 = ListNode(3)
l1_2 = ListNode(8)
l1_3 = ListNode(11)
l1_4 = ListNode(15)
l1_0.next = l1_1
l1_1.next = l1_2
l1_2.next = l1_3
l1_3.next = l1_4

# 建立链表:2->None
l2_0 = ListNode(2)

s1 = Solution().merge_two_lists(l1_0, l2_0)
while s1:
    print s1.val
    s1 = s1.next

# 测试代码2,建立链表:1->3->8->11->15->None
l1_0 = ListNode(1)
l1_1 = ListNode(3)
l1_2 = ListNode(8)
l1_3 = ListNode(11)
l1_4 = ListNode(15)
l1_0.next = l1_1
l1_1.next = l1_2
l1_2.next = l1_3
l1_3.next = l1_4

# 建立链表:2->None
l2_0 = ListNode(2)

s2 = Solution().merge_two_lists_recursive(l1_0, l2_0)
while s2:
    print s2.val
    s2 = s2.next

相关文章

  • 面试题25. 合并两个排序的链表

    合并两个排序的链表 题目描述 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例: ...

  • LeetCode题解之合并两个排序的链表

    合并两个排序的链表 题目描述 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1:...

  • 25:合并两个排序的链表

    题目25:合并两个排序的链表 输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的 举例说...

  • LeetCode 每日一题 [56] 合并两个排序的链表

    LeetCode 合并两个排序的链表 [简单] 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增...

  • leecode刷题(27)-- 合并k个排序链表

    leecode刷题(27)-- 合并k个排序链表 合并k个排序链表 合并 k 个排序链表,返回合并后的排序链表。请...

  • 剑指offer之合并两个排序的列表

    合并两个排序的列表 欢迎关注作者简书csdn传送门 题目   输入两个递增排序的链表,合并这两个链表并使新链表中的...

  • 2018-12-26

    问题列表 合并两个有序链表 合并K个排序链表 合并区间 插入区间 问题与反馈 总结与收获 多个有序链表的合并,类似...

  • 面试题25:合并两个排序的链表

    题目:输入两个递增排序的链表,合并这两个链表并使新链表中的节点依然是排序的

  • [LeetCode OJ]- Merge Two Sorted

    题目要求:合并两个单向已排序的链表l1和l2,返回新的链表。 思路:该问题跟合并两个已排序的数组很像,合并两个已排...

  • 链表

    1 合并两个链表 2 链表判环 并返回入环节点的值 3 两个无环单链表是否相交 4 合并两个有序链表 5 链表排序

网友评论

      本文标题:合并两个排序链表

      本文链接:https://www.haomeiwen.com/subject/zpuvaxtx.html