专栏首页小浩算法《剑指offer》第21天:合并两个有序链表

《剑指offer》第21天:合并两个有序链表

01、题目分析

第21题:合并两个有序链表

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

示例:

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

首先我们拿到题目乍眼一看,类似这种链表的合并问题。基本上马上可以想到需要设置一个哨兵节点,这可以在最后让我们比较容易地返回合并后的链表。(不懂哨兵节点的同学,可以先移驾到 06.删除链表倒数第N个节点(19) 进行学习)

假设我们的链表分别为:

l1 = [1,2,4]

l2 = [1,3,4]

同时我们设定一个 "prehead" 的哨兵节点,大概是下面这样:

02、题目图解

如上图所示,首先我们维护一个 prehead 的哨兵节点。我们其实只需要调整它的 next 指针。让它总是指向 l1 或者 l2 中较小的一个,直到 l1 或者 l2 任一指向 null。这样到了最后,如果l1还是l2中任意一方还有余下元素没有用到,那余下的这些元素一定大于prehead已经合并完的链表(因为是有序链表)。我们只需要将这些元素全部追加到prehead合并完的链表后,最终就得到了我们需要的链表。大概流程如下:

  1. 首先我们将 prehead 指向 l1 或者 l2 中比较小的一个。如果相等,则任意一个都可以。此时的 l1 为 [2,4],l2 为 [1,3,4]
  1. 我们继续上面的步骤。将 prehead 的链表指向 l1 和 l2 中较小的一个。现在这里就是指向1。
  1. 反复上图步骤。
  1. 现在 prehead.Next 就是我们需要的链表。

03、Go语言示例

根据以上分析,我们可以得到下面的题解:

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    prehead := &ListNode{}
    result := prehead
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            prehead.Next = l1
            l1 = l1.Next
        }else{
            prehead.Next = l2
            l2 = l2.Next
        }
        prehead = prehead.Next
    }
    if l1 != nil {
        prehead.Next = l1
    }
    if l2 != nil {
        prehead.Next = l2
    }
    return result.Next
}

再给出java版:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode();
        ListNode result = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                prehead.next = l1;
                l1 = l1.next;
            }else{
                prehead.next = l2;
                l2 = l2.next;
            }
            prehead = prehead.next;
        }
        if (l1 != null) {
            prehead.next = l1;
        }
        if (l2 != null) {
            prehead.next = l2;
        }
        return result.next;
    }
}

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:如何合并两个有序链表

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

    程序员小浩
  • 漫画:位运算系列篇(只出现一次的数字 - 进阶版)

    今天是小浩算法“365刷题计划”第63天。今天状态不好,因为昨天感冒了,写了好久才写下这篇长文,本来说写点别的水一水,改天再做这个续集,但是想了想还是算了!昨天...

    程序员小浩
  • 《剑指offer》第24天:链表相加

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

    程序员小浩
  • LinkedList - 2. Add Two Numbers

    You are given two non-empty linked lists representing two non-negative integers....

    用户5705150
  • LeetCode - 两数相加

    原题地址: https://leetcode-cn.com/problems/add-two-numbers/

    晓痴
  • PhpStorm提示interpreter is not configured解决方法

    返回PhpStorm软件,右下角提示"interpreter is not configured Please configure PHP Interprete...

    德顺
  • 【Netty】服务端和客户端

    1、创建ServerBootStrap实例 2、设置并绑定Reactor线程池:EventLoopGroup,EventLoop就是处理所有注册到本线程的Sel...

    用户3467126
  • 【漫画科普】什么是PAM4

    所以,他就和小白约定:考试的时候,自己会吹泡泡,吹大泡泡代表1(对),吹小泡泡代表0(错)。

    鲜枣课堂
  • 还在为线上服务Docker容器权限问题烦恼吗,或许这款神器能助你彻底解决它!

    GoTTY 是一个简单的基于 Go 语言的命令行工具,它可以将你的终端(TTY)作为 Web 程序共享。GoTTY 的架构是基于 Hterm + Web Soc...

    我的小碗汤
  • 拐点来临:SSD年内出货量有望首超HDD!

    2018年存储市场有望发生标志性事件:SSD出货量首次超过HDD,迎来市场真正的拐点!

    大数据在线

扫码关注云+社区

领取腾讯云代金券