当前位置: 首页 > article >正文

合并两个有序数组(88)合并两个有序链表(21)

88. 合并两个有序数组 - 力扣(LeetCode)

21. 合并两个有序链表 - 力扣(LeetCode)

解法(88):

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        for (; m > 0; --m){
            for (; n > 0; --n) {
                //从两个数组的尾->头开始比较
                if (nums1[m - 1] <= nums2[n - 1]) {
                    nums1[m + n - 1] = nums2[n - 1];
                }else {
                    nums1[m + n - 1] = nums1[m - 1];
                    break;
                }
            }
            if (n == 0) {
                break;
            }
        }  

       if (n > 0) {
            for (int i = 0; i < n; ++i) {
                nums1[i] = nums2[i];
            }
        }

    }
};

解法(21):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        if (list2 == nullptr) {
            return list1;
        }

        if (list1 == nullptr) {
            return list2;
        }

        ListNode * tmp1 = list1;
        ListNode * tmp2 = list2;
        //用来记录tmp1 指针的 pre 指针
        ListNode * tmp1_pre = nullptr;

        while (tmp1 != nullptr && tmp2 != nullptr) {
            ListNode * next1_ = tmp1->next;
            ListNode * tmp2_ = tmp2;
            
            if (tmp1->val == tmp2->val) {
                tmp2 = tmp2->next;
                tmp1->next = tmp2_;
                tmp2_->next = next1_;
            }else if (tmp1->val > tmp2->val) {
                tmp2 = tmp2->next;
                swap(tmp1->val, tmp2_->val);
                tmp1->next = tmp2_;
                tmp2_->next = next1_;
            }

            tmp1_pre = tmp1;
            tmp1 = tmp1->next;
        }

        if (tmp2 != nullptr) {
            tmp1_pre->next = tmp2;
        }

        return list1;
    }

    
};

总结:

(88)和(21)的时间复杂度都是O(m+n),空间复杂度都是O(1)。这里面有序数组为了做到空间复杂度O(1),需要从尾->头开始进行比较,而有序链表因为允许随机insert和delete,所以从头->尾开始进行比较


http://www.kler.cn/a/510505.html

相关文章:

  • Java 对象池管理的高性能工具库 Apache Commons Pool 2
  • PHP 8.4 安装和升级指南
  • 麒麟系统下载依赖到本地
  • 使用 Helm 安装 Redis 集群
  • 向harbor中上传镜像(向harbor上传image)
  • python mysql库的三个库mysqlclient mysql-connector-python pymysql如何选择,他们之间的区别
  • 大模型UI:Gradio全解11——Chatbot:融合大模型的聊天机器人(4)
  • 第34天:Web开发-PHP应用鉴别修复AI算法流量检测PHP.INI通用过滤内置函数
  • 《weak_ptr源码剖析》
  • 在K8S中,业务Pod数据如何存储?
  • JavaScript系列(32)-- WebAssembly集成详解
  • 数据库高可用方案-08-多版本管理
  • owasp SQL 注入-03 (原理)
  • Python爬虫-爱奇艺电视剧数据
  • Redis的部署和操作
  • 基于poll函数实现并发处理
  • 联合体(Union)
  • 根据现代业务需求设计数据架构(三)- 数据网格(Data Mesh)
  • 数据结构 数组
  • 团体程序设计天梯赛-练习集——L1-012 计算指数
  • Netty中的NioEventloop(1)
  • vue基础代码第一篇
  • 分类问题(二元,多元逻辑回归,费歇尔判别分析)spss实操
  • [手机Linux] ubuntu 错误解决
  • lanqiaoOJ 2128:重新排序 ← 一维差分
  • 【优先算法】滑动窗口--结合例题详解学习