(链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了(链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓剑指 Offer 25. 合并两个排序的链表

难度:简单

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

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

限制

  • 0 <= 链表长度 <= 1000

注意:本题与 21. 合并两个有序链表 相同

💡思路:

法一:递归

将该问题可以分解成子链表,只比较当前 l1 链表 和 l2 链表 的头结点,取最小加入合并的链表中,并将最小结点的来自的链表的头结点往后移一位,在递归调用 mergeTwoLists 函数。

法二:迭代

我们可以用迭代的方法来实现上述算法。当 l1l2 都不是空链表时,判断 l1l2 哪一个链表的头节点的值更小,将较小值的节点添加到结果里,当一个节点被添加到结果里之后,将对应链表中的节点向后移一位。

🍁代码:(C++、Java)

法一:递归
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }else{
	        l2->next = mergeTwoLists(l1, l2->next);
	        return l2;
	    }
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

法二:迭代
C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;
        //先找到头结点
        ListNode* head = nullptr;
        if(l1->val <= l2->val){
            head = l1;
            l1 = l1->next;
        }else{
            head = l2;
            l2 = l2->next;
        }
        //合并
        ListNode* cur = head;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1 == nullptr){
            cur->next = l2;
        }else{
            cur->next = l1;
        }
        return head;
    }
};

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        //先找到头结点
        ListNode head = null;
        if(l1.val <= l2.val){
            head = l1;
            l1 = l1.next;
        }else{
            head = l2;
            l2 = l2.next;
        }
        //合并
        ListNode cur = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 == null){
            cur.next = l2;
        }else{
            cur.next = l1;
        }
        return head;
    }
}
🚀 运行结果:

(链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】,LeetCode,链表,leetcode,数据结构

🕔 复杂度分析:
  • 时间复杂度 O ( n + m ) O(n+m) O(n+m),其中 nm 分别为两个链表的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),迭代法只需要常数的空间存放若干变量。而法一递归的空间复杂度为 O ( n + m ) O(n+m) O(n+m),递归调用 mergeTwoLists 函数时需要消耗栈空间,栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用 n+m 次,因此空间复杂度为 O ( n + m ) O(n+m) O(n+m)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-610637.html

注: 如有不足,欢迎指正!

到了这里,关于(链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】剑指 Offer(25)

    目录 题目:剑指 Offer 49. 丑数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 丑数这道题用到一点动态规划的思想, 具体思路如下: 根据题意: 如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数, 那么我们发现,之后的丑数: 都是前

    2023年04月09日
    浏览(47)
  • 剑指 Offer 52. 两个链表的第一个公共节点

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸剑指 Offer  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸

    2024年02月10日
    浏览(36)
  • 【C/C++练习】合并k个已排序的链表

    前言:  今天给大家分享一道面试中常见的题目——合并K个升序链表,我会用暴力和分治两钟方法去求解这道题目,通过动图展示问题求解的全过程。这里提醒大家,画图是我们求解复杂问题的有效手段,有时可以起到事半功倍的效果,各位小伙伴在做题的过程中如果遇到

    2024年02月09日
    浏览(37)
  • LeetCode 剑指offer 09.用两个栈实现队列

    用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 这道题很简单,主要理解栈与队列的区别,注意细节就可以 c++ Go

    2024年02月09日
    浏览(33)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(47)
  • Leetcode-每日一题【剑指 Offer 06. 从尾到头打印链表】

    输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 示例 1: 输入: head = [1,3,2] 输出: [2,3,1] 限制: 0 = 链表长度 = 10000 1.题目要求我们从尾到头反过来返回每个节点的值,这道题我们可以用栈去解决,但是我们还可以采用另一种方法。就是我们可以

    2024年02月13日
    浏览(34)
  • (栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】

    难度:简单 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素, deleteHead 操作返回 -1 ) 示例 1: 输入: [“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“d

    2024年02月17日
    浏览(40)
  • Leetcode-每日一题【剑指 Offer 35. 复杂链表的复制】

    请实现  copyRandomList  函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个  next  指针指向下一个节点,还有一个  random  指针指向链表中的任意节点或者  null 。 示例 1: 输入: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出: [[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2: 输入

    2024年02月11日
    浏览(41)
  • 【Leetcode -1290.二进制链表转整数 -剑指Offer 06.从尾到头打印链表】

    题目:给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。请你返回该链表所表示数字的十进制值 。 示例 1: 输入:head = [1, 0, 1] 输出:5 解释:二进制数(101) 转化为十进制数(5) 示例 2: 输入:head = [0] 输出:

    2023年04月26日
    浏览(41)
  • 【LeetCode-中等】剑指 Offer 36. 二叉搜索树与双向链表

    剑指 Offer 36. 二叉搜索树与双向链表 后序遍历、二叉搜索树 二叉搜索树中的任一节点的 直接前驱为其左子树的最右侧节点,直接后继为其右子树的最左侧节点 。因此,可以通过这个关系来操作原来的二叉树。 为了不影响深度较大的节点的判断,使用后序遍历。 Step1. 后序遍

    2024年02月13日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包