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

L6.【LeetCode笔记】合并两个有序链表

1.题目

https://leetcode.cn/problems/merge-two-sorted-lists/

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

示例 1:

f30bf84707351f6d3a2cead840a19fc7.jpeg

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1l2 均按 非递减顺序 排列
  • 代码模版
  • /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
    {
    }

2.自解

一个容易想到的解法:取小的尾插(开一个新的链表)

对于链表list1和list2,可以另外开一个新的链表,再将list1和list2的val复制进新链表的节点,最后返回新链表的头结点的地址即可

不加思索写出以下代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{struct ListNode* cur1=list1;struct ListNode* cur2=list2;if (list1==NULL)return list2;if (list2==NULL)return list1;struct newListNode{int new_val;struct ListNode* new_next;};struct newListNode* new_next=NULL;struct newListNode* newhead=NULL;struct newListNode* m_m_new=(struct newListNode*)malloc(sizeof(struct newListNode));newhead=m_m_new;newhead->new_next=NULL;struct newListNode* new_cur=newhead;while(cur1!=NULL && cur2!=NULL){if (cur1==NULL){new_cur->new_val=cur2->val;cur2=cur2->next;//分配新结点的空间struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;new_cur=m_new;continue;}if (cur2==NULL){new_cur->new_val=cur1->val;cur1=cur1->next;struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;new_cur=m_new;continue;}if (cur1->val<=cur2->val){new_cur->new_val=cur1->val;cur1=cur1->next;struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;new_cur=m_new;}else{new_cur->new_val=cur2->val;cur2=cur2->next;//分配新结点的空间struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;new_cur=m_new;}}new_cur->new_next=NULL;new_cur=NULL;return newhead;
}

运行时出现问题

75c71bd74f524c6faa7bc7b8733a78ea.png

发现while循环的条件写错了!!

应该改成

while(!(cur1==NULL && cur2==NULL))

完整代码

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{struct ListNode* cur1=list1;struct ListNode* cur2=list2;if (list1==NULL)return list2;if (list2==NULL)return list1;struct newListNode{int new_val;struct ListNode* new_next;};struct newListNode* new_next=NULL;struct newListNode* newhead=NULL;struct newListNode* m_m_new=(struct newListNode*)malloc(sizeof(struct newListNode));newhead=m_m_new;newhead->new_next=NULL;struct newListNode* new_cur=newhead;struct newListNode* before_new_cur=NULL;while(!(cur1==NULL && cur2==NULL)){if (cur1==NULL){new_cur->new_val=cur2->val;cur2=cur2->next;struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;before_new_cur=new_cur;new_cur=m_new;new_cur->new_next=NULL;continue;}if (cur2==NULL){new_cur->new_val=cur1->val;cur1=cur1->next;struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;before_new_cur=new_cur;new_cur=m_new;continue;}if (cur1->val<=cur2->val){new_cur->new_val=cur1->val;cur1=cur1->next;struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;new_cur=m_new;}else{new_cur->new_val=cur2->val;cur2=cur2->next;           struct newListNode* m_new=(struct newListNode*)malloc(sizeof(struct newListNode));new_cur->new_next=m_new;new_cur=m_new;}}before_new_cur->new_next=NULL;return newhead;
}

before_new_cur是当cur1===NULL或cur2==NULL,备份new_cur的前一个节点的地址

提交结果

6bbfcd94198846fba7ea978f264e0a9b.png

3.其他解法

方法1:取小的尾插(不开新链表)

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{struct ListNode* cur1=list1;struct ListNode* cur2=list2;struct ListNode* head=NULL;struct ListNode* tail=NULL;if (list1==NULL)return list2;if (list2==NULL)return list1;while (cur1 && cur2){if (cur1->val<cur2->val){if (head==NULL){head=tail=cur1;}else{tail->next=cur1;tail=tail->next;}cur1=cur1->next;}else{if (head==NULL){head=tail=cur2;}else{tail->next=cur2;tail=tail->next;}cur2=cur2->next;           }}if(cur1)tail->next=cur1;if(cur2)tail->next=cur2;return head;
}

分析

尾插要有尾指针tail(这样不用频繁找尾),同时要有指向头节点的指针head用于返回

cur1->val<cur2->val和cur1->val>=cur2->val操作方式是类似的

相关文章:

L6.【LeetCode笔记】合并两个有序链表

1.题目 https://leetcode.cn/problems/merge-two-sorted-lists/ 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]示例 2&…...

讲解Golang选择语句

Golang选择语句 1. if 语句1.1 基本语法1.2 if-else 语句1.3 if-else if-else 语句1.4 简短声明和初始化1.5 多个条件的逻辑运算 2. switch 语句2.1 基本语法2.2 示例2.3 switch 语句与 if 的对比2.4 不指定表达式2.5 fallthrough 语句2.6 case 支持多个值 3. 总结 Go语言中的选…...

练习LabVIEW第四十一题

学习目标&#xff1a; 编写一个程序测试自己在程序前面板上输入一段文字“CSDN是一个优秀的网站”所用的时间。 开始编写&#xff1a; 前面板放置一个数值显示控件&#xff0c;程序框图添加顺序结构共三帧&#xff0c;第一帧放一个获取日期/时间&#xff08;秒&#xff09;函…...

应对AI与机器学习的安全与授权管理新挑战,CodeMeter不断创新引领保护方案

人工智能&#xff08;AI&#xff09;和机器学习&#xff08;ML&#xff09;技术正在快速发展&#xff0c;逐渐应用到全球各类主流系统、设备及关键应用场景中&#xff0c;尤其是在政府、商业和工业组织不断加深互联的情况下&#xff0c;AI和ML技术的影响日益广泛。虽然AI技术的…...

【2024最新版Kotlin教程】Kotlin第一行代码系列第五课-类继承,抽象类,接口

【2024最新版Kotlin教程】Kotlin第一行代码系列第五课-类继承&#xff0c;抽象类&#xff0c;接口 为什么要有继承呢&#xff0c;现实中也是有继承的&#xff0c;对吧&#xff0c;你继承你爸的遗产&#xff0c;比如你爸建好了一个房子&#xff0c;儿子继承爸&#xff0c;就得了…...

虚拟现实和增强现实技术,如何打造沉浸式体验?

内容概要 在这个科技飞速发展的时代&#xff0c;虚拟现实&#xff08;VR&#xff09;与增强现实&#xff08;AR&#xff09;技术的结合就像调皮的小精灵&#xff0c;一下子把我们的生活变得神奇又有趣。想象一下&#xff0c;你正在游戏中与精灵搏斗&#xff0c;突然间身边的客…...

ChatGPT任务设计和微调策略的优化

目录 ChatGPT任务设计和微调策略的优化 一、GPT-3的基础 二、任务设计和微调策略的优化 三、基于人类反馈的强化学习(RLHF) 举例 完全注意力机制的自回归解码器网络 一、定义与原理 二、举例说明 ChatGPT任务设计和微调策略的优化 ChatGPT确实是从GPT-3开始,通过任…...

通过 SSH 连接远程 Ubuntu 服务器

目录 安装 SSH 服务器允许 SSH 通过防火墙远程 SSH 连接&#xff08;选&#xff09;重启向日葵 安装 SSH 服务器 更新软件包列表 sudo apt update安装 OpenSSH 服务器 sudo apt install openssh-server检查 SSH 服务器状态 sudo systemctl status ssh如果 SSH 服务器正在运…...

Perl 环境安装

Perl 环境安装 Perl 是一种广泛使用的高级、通用、解释型、动态编程语言。它最初由 Larry Wall 在 1987 年设计,现在由 Perl 5 和 Perl 6 两个主要版本组成。Perl 适合于多种编程任务,包括系统管理、Web 开发、网络编程、游戏开发等。在开始使用 Perl 进行编程之前,您需要在…...

【NOIP提高组】引水入城

【NOIP提高组】引水入城 &#x1f490;The Begin&#x1f490;点点关注&#xff0c;收藏不迷路&#x1f490; 在一个遥远的国度&#xff0c;一侧是风景秀美的湖泊&#xff0c;另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊&#xff0c;刚好构成一个N行M列的矩形&#xff…...

openvino python推理demo

openvino python推理demo import openvino from openvino.runtime import Core import numpy as np import argparse import hashlib import os import ioclass OpenvinoInfer:def __init__(self,device_id0):self.device_iddevice_idself.ie Core()self.available_devices …...

JavaWeb项目-----博客系统

一.设计数据库 1.创建数据库 create database if not exists java108_blog_system character set utf8; drop table if exists user; drop table if exists blog;2.创建博客列表 create table blog(blogId int primary key auto_increment,title varchar(20),content varcha…...

GY-56 (VL53L0X) 激光测距

文章目录 一、GY-56 简介二、引脚功能三、通信协议1.串口协议&#xff1a; 当 GY-56 PS 焊点开放时候使用(默认)&#xff08;1&#xff09;串口通信参数&#xff08;默认波特率值 9600bps&#xff09;&#xff08;2&#xff09;模块输出格式&#xff0c;每帧包含 8-13 个字节&a…...

当今陪玩系统小程序趋势,陪玩系统源码搭建后的适用于哪些平台

一、市场规模持续扩大 随着全球游戏市场的不断膨胀&#xff0c;游戏陪玩行业正逐渐从一个新兴领域成长为游戏产业链中不可或缺的一环。据《2024年1~6月中国游戏产业报告》显示&#xff0c;今年上半年&#xff0c;国内游戏市场实际销售收入达到1472.67亿元&#xff0c;同比增长…...

qt QListWidget详解

1、概述 QListWidget 是 Qt 框架中的一个类&#xff0c;它提供了一个基于模型的视图&#xff0c;用于显示项目的列表。QListWidget 继承自 QAbstractItemView 并为项目列表提供了一个直观的接口。与 QTreeView 和 QTableView 不同&#xff0c;QListWidget 是专门为单行或多行项…...

java ssm 校园快递物流平台 校园快递管理系统 物流管理 源码 jsp

一、项目简介 本项目是一套基于SSM的校园快递物流平台&#xff0c;主要针对计算机相关专业的和需要项目实战练习的Java学习者。 包含&#xff1a;项目源码、数据库脚本、软件工具等。 项目都经过严格调试&#xff0c;确保可以运行&#xff01; 二、技术实现 ​后端技术&#x…...

西安电子科技大学考研网报审核通过了,然后呢?

报考西安电子科技大学的宝贝们&#xff0c;考研网上确认已经截止的同学们&#xff0c;不用担心&#xff01; 最近&#xff0c;有很多同学问到一个问题&#xff1a;网上确认时看到有消息说禁止使用海马体照片&#xff0c;但我明明用了海马体的照片&#xff0c;审核却通过了&…...

pandas习题 051:将字符串数据读取到 DataFrame

编码题)有以下逗号隔开和空格隔开的字符串数据,如何将它读取为 DataFrame ? data = ‘’’ a,b,c 1,3,4 2,4,5 ‘’’ data2 = ‘’’ a b c 1 13 214 2 4 15 ‘’’ Python 代码如下:import pandas as pd import iodata = a,b,c 1,3,4 2,4,5 df = pd.read_csv(io.Stri…...

改进探路者算法复现

本文所涉及所有资源均在 传知代码平台 可获取。 目录 一、背景及意义介绍 (一)背景 ࿰...

PostgreSQL 学习笔记:PostgreSQL 主从复制

PostgreSQL 笔记&#xff1a;PostgreSQL 主从复制 博客地址&#xff1a;TMDOG 的博客 在现代应用程序中&#xff0c;数据库的高可用性和扩展性是至关重要的。PostgreSQL 提供了主从复制功能&#xff0c;可以在多个数据库实例之间复制数据&#xff0c;以实现冗余和负载均衡。本…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...