LeetCode 21：合并两个有序链表 Merge Two Sorted Lists

LeviDing 发布于2019-07-31 11:31 / 3345人阅读

摘要：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。无非是依次将两个链表每个节点的值对比，取出值较小的节点，添加到新链表末尾。将剩余链表传回递归函数。

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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.

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解题思路：

迭代和递归都能解题。无非是依次将两个链表每个节点的值对比，取出值较小的节点，添加到新链表末尾。然后继续比较两个链表，直到其中一个链表遍历完成，此时另一个链表剩余所有节点直接添加到新链表之后即可。其逻辑为：

原链表：1->2->4->null，1->3->4->5->6->null
依次对比节点值，取出各自头节点：1 = 1
值相同取出一个节点 1，组成新链表：1
此时原链表：2->4->null，1->3->4->5->6->null对比头节点值：2 > 1
取出 1 节点，添加到新链表末尾：1->1
此时原链表：2->4->null，3->4->5->6->null
对比头节点值：2 < 3
取出 2 节点，添加到新链表末尾：1->1->2
此时原链表：4->null，3->4->5->6->null
.......依次类推，直到其中一个原链表为空时：
原链表：null，4->5->6->null
新链表：1->1->2->3->4
这时其中一个原链表已经为空，则直接将另一个原链表添加到新链表末尾即可：
1->1->2->3->4->4->5->6->null

迭代法：

迭代法需要注意：先判断原链表是否为空；对比原链表第一个节点值的大小，选择较小一个作为新链表的头节点。之后才能按上述逻辑执行。

如果添加一个虚拟节点作为头节点，则无需上述条件，但应当返回虚拟节点的下一个节点。

Java：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);//新建虚拟头节点
        ListNode cur = head;//当前节点指向虚拟头节点
        while (l1 != null && l2 != null) {//循环条件为链表都不为空
            if (l1.val < l2.val) {//比较头节点的值的大小
                cur.next = l1;//当前节点连接到节点值较小的一个
                l1 = l1.next;//刷新原链表头节点
                cur = cur.next;//刷新当前节点
            } else {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }
        if (l1 == null) cur.next = l2;//选择另外一个不为空的原链表，连接到新链表末尾
        else cur.next = l1;
        return head.next;//返回虚拟头节点的下一个节点，即真实头节点
    }
}

Python3：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(-1)
        cur = head;
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = l2
                cur = cur.next
                l2 = l2.next
        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return head.next

递归法：

递归基线条件为：原链表其中之一遇到空节点。返回值为：另一个链表剩余部分的头节点。

递归判断头节点的值的大小，取小的节点添加到新链表之后。将剩余链表传回递归函数。

Java：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;//基线条件
        if (l2 == null) return l1;//基线条件
        ListNode head;
        if (l1.val <= l2.val) {//选择节点值较小的节点
            head = l1;//刷新头节点
            head.next = mergeTwoLists(l1.next, l2);//剩余链表作为参数传入递归函数
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

Python3：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val <= l2.val:
            head = l1
            head.next = self.mergeTwoLists(l1.next, l2)
        else:
            head = l2
            head.next = self.mergeTwoLists(l1, l2.next)
        return head

欢迎关注微.信公.众号：爱写Bug

GPU云服务器云服务器合并链表的c语言合并两个单链表 linux 两个硬盘合并 js 两个数据合并

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

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

LeetCode 之 JavaScript 解答第21题 —— 合并两个有序链表（Merge Two

摘要：什么意思呢比如上方合并链表的代码，分别明确函数的参数和返回值是什么参数是两个合并的链表结点头结点。返回值是合并后的链表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿题目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 评论0 收藏0
leetcode21 Merge Two Sorted Lists 将两个有序链表组合成一个新的有

摘要：题目要求翻译过来就是将两个有序的链表组合成一个新的有序的链表思路一循环在当前两个链表的节点都是非空的情况下比较大小，较小的添入结果链表中并且获得较小节点的下一个节点。题目要求 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing togeth...

BothEyes1993 2019-08-14 18:05 评论0 收藏0
Leetcode 21 Merge Two Sorted Lists

摘要：题目详情题目要求我们将两个有序链表合成一个有序的链表。输入输出想法首先要判断其中一个链表为空的状态，这种情况直接返回另一个链表即可。每次递归都会获得当前两个链表指针位置的值较小的节点，从而组成一个新的链表。题目详情 Merge two sorted linked lists and return it as a new list. The new list should be mad...

xbynet 2019-08-14 18:01 评论0 收藏0
LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿题目：Merge K...

zhou_you 2019-08-23 16:53 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0