当前位置: 首页 > 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;以实现冗余和负载均衡。本…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...