合并两个已排序的链表

ormsf 发布于2019-07-25 12:04 / 3287人阅读

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

合并两个已排序的链表 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，比较a和b节点内值的大小，将较小的加入tail之后，a和b中较小的向后移动一个节点，较大的不动，tail向后移动一个节点保证任意时候指向都是新链表尾部

l1和l2其中一个已经遍历完，若另一个还有元素，添加到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地址

云服务器 GPU云服务器链表排序合并链表的c语言链表排序算法合并排序

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

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

合并n个已排序的链表

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

HtmlCssJs 2019-07-30 14:19 评论0 收藏0
剑指offer:合并两个排序的链表（Java）

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

darkbaby123 2019-08-16 18:39 评论0 收藏0
用 JavaScript 实现链表操作 - 15 Merge Sort

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

X_AirDu 2019-08-20 14:23 评论0 收藏0
【刷算法】合并两个排序的单链表

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

2501207950 2019-08-22 18:26 评论0 收藏0