资讯专栏INFORMATION COLUMN

合并两个已排序的链表

ormsf / 3175人阅读

摘要:合并两个已排序的链表合并两个已排序的链表,新链表中的每个节点必须是来自输入的两个链表的节点即不能构造新的节点,返回新链表的头部。

合并两个已排序的链表 Merge Two Sorted Lists

合并两个已排序的链表,新链表中的每个节点必须是来自输入的两个链表的节点(即不能构造新的节点),返回新链表的头部。

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

example 1

input: 1->2->4, 3->8
output: 1->2->3->4->8

思路

head指向输入两个链表中头节点较小值,作为新链表的头部

tail指向新链表表尾,初始状态head = tail

a扫描l1,b扫描l2,比较ab节点内值的大小,将较小的加入tail之后,ab中较小的向后移动一个节点,较大的不动,tail向后移动一个节点保证任意时候指向都是新链表尾部

l1l2其中一个已经遍历完,若另一个还有元素,添加到tail之后

代码
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if None in (l1, l2):
            return l1 or l2
        head = tail = l1 if l1.val <= l2.val else l2
        a = l1 if l1.val > l2.val else l1.next
        b = l2 if l1.val <= l2.val else l2.next
        while a and b:
            if a.val <= b.val:
                tail.next = a
                tail, a = tail.next, a.next
            else:
                tail.next = b
                tail, b = tail.next, b.next
        tail.next = a or b
        return head

本题以及其它leetcode题目代码github地址: github地址

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/38662.html

相关文章

  • 合并n个排序链表

    摘要:合并个已排序的链表合并个已排序的链表,新链表中的每个节点必须是来自输入的原链表的节点即不能构造新的节点,返回新链表的头部。思路参照本人之前已发表的合并两个已排序的链表,只需要将此算法应用次即可得到新链表。 合并n个已排序的链表 Merge k Sorted Lists 合并n个已排序的链表,新链表中的每个节点必须是来自输入的原链表的节点(即不能构造新的节点),返回新链表的头部。 Me...

    HtmlCssJs 评论0 收藏0
  • 剑指offer:合并两个排序链表(Java)

    摘要:问题描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 1.问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 2.思路 方法1:非递归方法 根据题目这个很类似排序中的外排过程,两个数组分别排好序,然后再把他们整体进行排序.所以这道题思想很简单,就是用两个变量分别遍历两个链表.比较遍历到...

    darkbaby123 评论0 收藏0
  • 用 JavaScript 实现链表操作 - 15 Merge Sort

    摘要:需求实现函数进行归并排序。解法归并排序的运行方式是,递归的把一个大链表切分成两个小链表。切分到最后就全是单节点链表了,而单节点链表可以被认为是已经排好序的。这时候再两两合并,最终会得到一个完整的已排序链表。用把排好序的两个链表合并起来。 TL;DR 对链表进行归并排序,系列目录见 前言和目录 。 需求 实现函数 mergeSort() 进行归并排序。注意这种排序法需要使用递归。在 fr...

    X_AirDu 评论0 收藏0
  • 数据结构之链表OJ练习检验你链表水平是否合格

    摘要:同时让当前结点的指针指向,从而实现从链表尾部开始的局部反转当递归函数全部出栈后,链表反转完成。这个链表的倒数第个节点是值为的节点。新链表是通过拼接给定的两个链表的所有节点组成的。 目录 1.反转链表 K个一组翻转链表 链表的中间节点: 链表倒数第k个节点: 删除链表倒数第k个节...

    andycall 评论0 收藏0
  • 【刷算法】合并两个排序的单链表

    摘要:题目描述输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 分析 首先考虑两个链表的头部哪个成为新链表的头,显然是值小的那个是新的头;然后是合并时,两个链表上分别有一个指针cur1和cur2,比较两个指针指向的节点值大小,较小的链接到新链表的...

    2501207950 评论0 收藏0

发表评论

0条评论

ormsf

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<