【算法】链表相关

【ps】本篇有 5 道 leetcode OJ。 

一、算法简介

        链表是一种常见的线性数据结构,是一种在物理结构上非连续、非顺序的存储结构,其中的数据元素的逻辑顺序由其中的指针链接次序实现,指针链接的每一个结构体都是一个节点。

        链表的结构多种多样,有单向或双向、带头或不带头、循环或非循环之分。但实际中,最常用的是以下两种组合:

  • 无头单向非循环链表(或称单链表)

  • 带头双向循环链表(或称双向链表)

 【Tips】链表的常用技巧

  • 一定要画图!
  • 引入一个虚拟的头节点,利于处理边界情况、对链表进行各种操作。

  • 不要吝啬空间,大胆定义变量去使用,尤其涉及到插入操作的时候。

  • 快慢双指针,可以对链表判环、找环的入口、找链表中倒数第 n 个节点。

【Tips】链表的常见操作

  •  创建一个新节点
  • 尾插
  • 头插

二、相关例题

1)两数相加

2. 两数相加

.1- 题目解析

        要将两个链表的每个节点中的数相加并放在一个新的链表中,那一定就要构建一个链表,我们可以对这个新链表引入一个头节点,然后直接遍历两个链表进行求和,然后将结果构建出一个新节点尾插入头节点即可。

        特别的,我们单独定义一个变量 t,既保存相加的结果,又记录进位。

.2- 代码编写

/*** 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* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* newhead=new ListNode(0);ListNode*cur1=l1,*cur2=l2,*prev=newhead;int t=0; //保存求和结果+记录进位while(cur1||cur2||t){//取两个链表的节点进行求和if(cur1){t+=cur1->val;cur1=cur1->next;}if(cur2){t+=cur2->val;cur2=cur2->next;}prev->next=new ListNode(t%10);//取结果的个位t/=10;                        //取进位prev=prev->next;}prev=newhead->next;delete newhead;return prev;}
};

2)两两交换链表中的节点

24. 两两交换链表中的节点

.1- 题目解析

        以示例 1 为例。我们可以引入一个头节点,并定义四个指针变量来表示不同的节点。

        由此,要实现题目要求的交换,仅需交换 cur 和 next 指向的节点即可,然后将这四个指针整体向后移动,继续完成下次交换,直到 cur 遇到了空节点,说明此时整个链表都完成了交换。

.2- 代码编写

/*** 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* swapPairs(ListNode* head) {if(head==nullptr||head->next==nullptr)return head; //处理边界情况ListNode* newhead=new ListNode(0);newhead->next=head;ListNode* prev=newhead,*cur=newhead->next;ListNode* next=cur->next,*nnext=next->next;while(cur && next){//交换 cur 和 nextcur->next=nnext;next->next=cur;prev->next=next;//继续遍历链表prev=cur;cur=nnext;if(cur)next=cur->next;if(next)nnext=next->next;}cur=newhead->next;delete newhead;return cur;}
};

3)重排链表

重排链表. - 力扣(LeetCode)

.1- 题目解析

        以示例 1 为例。如果将原始链表从中间一分为二,将后半部分链表逆序,然后将前半部分和后半部分的链表节点依此插入道一个新链表中(前半部分先插入,后半部分后插入),就能得到题目要求的链表了。

         我们可以用快慢双指针来找到链表的中间位置,将后半部分的起始节点看作是慢指针的下一根节点,然后用头插法来对后半部分的链表进行逆序操作,这样无论原始链表的节点是单数还是复数,都不会影响操作的正确性。

         逆序完后半部分的链表之后,依此将前后两部分的链表插入到一个新的头节点之后即可。

.2- 代码编写

/*** 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:void reorderList(ListNode* head) {if(head==nullptr||head->next==nullptr||head->next->next==nullptr)return;//找到原始链表的中间位置ListNode* fast=head,*slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;}//头插法逆序后半部分ListNode* newhead=new ListNode(0);ListNode*cur=slow->next,*next=cur->next;slow->next=nullptr; //断开前后两个链表while(cur){next=cur->next;cur->next=newhead->next;newhead->next=cur;cur=next;            }//合并两个链表ListNode* ret=new ListNode(0);ListNode* prev=ret;ListNode* cur1=head,*cur2=newhead->next;while(cur1){prev->next=cur1;cur1=cur1->next;prev=prev->next;if(cur2){prev->next=cur2;cur2=cur2->next;prev=prev->next;}}delete newhead;delete ret;}
};

4)合并 K 个升序链表

23. 合并 K 个升序链表

.1- 题目解析

        要合并 K 个升序链表,可以先合并两个升序链表,再继续两两合并剩下的链表。我们可以用优先级队列(建小根堆排升序)来优化这个过程,将所有链表的头节点依此入队,即可找到最小的那个节点,只需将其尾插入一个新的头节点,然后将后续的节点入队,重复这个过程,就可以完成 K 个升序链表的合并了。

        另外,先合并两个升序链表,再继续两两合并剩下的链表,也可以用归并的方式来解决。

.2- 代码编写

//法1:优先级队列
/*** 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 {struct cmp{bool operator()(const ListNode* l1,const ListNode* l2){return l1->val > l2->val;}};
public: ListNode* mergeKLists(vector<ListNode*>& lists) {//创建一个小根堆priority_queue<ListNode*,vector<ListNode*>,cmp> heap;//让所有链表的头节点进行小根堆for(auto l: lists) if(l)heap.push(l);//合并链表ListNode* ret=new ListNode(0);ListNode* prev=ret;while(!heap.empty()){auto t=heap.top();//每次取堆顶元素heap.pop();prev->next=t;//链接prev=t;if(t->next) //将后续的节点入堆heap.push(t->next);}prev=ret->next;delete ret;return prev;}
};
//法2:递归
/*** 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* mergeKLists(vector<ListNode*>& lists) {return merge(lists,0,lists.size()-1);}ListNode* merge(vector<ListNode*>&lists,int left,int right){if(left>right)return nullptr;if(left==right)return lists[left];//平分数组int mid=(left+right)>>1;//递归处理左右区间ListNode* l1=merge(lists,left,mid);ListNode* l2=merge(lists,mid+1,right);//合并两个有序链表return mergeTowlist(l1,l2);}ListNode* mergeTowlist(ListNode* l1,ListNode* l2){if(l1==nullptr)return l2;if(l2==nullptr)return l1;ListNode head;ListNode* cur1=l1,*cur2=l2,*prev=&head;head.next=nullptr;while(cur1&&cur2){if(cur1->val<=cur2->val){prev->next=cur1;prev=cur1;cur1=cur1->next;}else{prev->next=cur2;prev=cur2;cur2=cur2->next;}}if(cur1)prev->next=cur1;if(cur2)prev->next=cur2;return head.next;}
};

5)K 个一组翻转链表

25. K 个一组翻转链表

.1- 题目解析

.2- 代码编写

/*** 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* reverseKGroup(ListNode* head, int k) {//1.先求出需要逆序多少组int n=0;ListNode* cur=head;while(cur){cur=cur->next;n++;}n/=k;//2.重复n次,长度为k的链表逆序ListNode* newHead=new ListNode(0);ListNode* prev=newHead;cur=head;for(int i=0;i<n;i++){ListNode* tmp=cur;for(int j=0;j<k;j++){ListNode* next=cur->next;cur->next=prev->next;prev->next=cur;cur=next;}prev=tmp;}prev->next=cur;cur=newHead->next;delete newHead;return cur;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/421230.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于C#+SQL Server2008 开发三层架构(CS界面)图书管理系统

图书管理系统 一、项目背景及意义 当今由于信息技术的飞速发展&#xff0c;图书馆作为社会知识信息媒介的功能日益重要&#xff0c;网络环境下的信息资源建设知识仓库的设计&#xff0c;开放存取学术交流模式&#xff0c;知识管理系统&#xff0c;智能检索&#xff0c;数字参…

文件存储阿里云

1.图片存储 图片存储是指将图片文件保存在服务器或云存储中的技术或服务。图片存储的主要目的是方便用户上传、存储、管理和分享图片文件。 图片存储可以分为两种主要类型&#xff1a;本地存储和云存储。 本地存储是将图片文件保存在本地服务器或计算机上的一种方式。这种存…

区块链学习笔记2--区块链技术的形成 以太坊

分布式数据存储&#xff1a; 在每个参与者电脑上备份 账本实时同步和对账 点对点通信 共识机制 加密算法&#xff1a; 对用户个人信息的加密 转账过程中的签名授权 账本一致性校验 挖矿算法的目标hash 区块链2.0技术 以太坊 比特币的出现让经济贸易变得简单&#xff0c;而比特…

LabVIEW环境中等待FPGA模块初始化完成

这个程序使用的是LabVIEW环境中的FPGA模块和I/O模块初始化功能&#xff0c;主要实现等待FAM&#xff08;Field-Programmable Gate Array Module&#xff0c;FPGA模块&#xff09;的初始化完成&#xff0c;并处理初始化过程中的错误。让我们逐步分析各部分的功能&#xff1a; 1.…

[ACTF2020 新生赛]Upload1

1、点开题目链接&#xff0c;页面显示如下&#xff0c;上传test.jpg里面包含一句话木马 GIF89a? <script language"php">eval($_REQUEST[1])</script> 2、使用bp抓包修改后缀&#xff0c;点击发送 3、不关浏览器的代理&#xff0c;在bp中将该包放行 4、…

HyperWorks中的Size and bias 子面板

此面板是 automesh 经常使用的子面板&#xff0c;通过此面板&#xff0c;用户可用设置单元尺寸、单元类型以及以及映射类型等多种控制选项&#xff0c;然后通过预览按钮查看待生成网格模型的状态。 图 3-6 size and bias 子面板 1.Density&#xff08;密度&#xff09; Adjus…

【系统分析师】计算机组成与体系架构

计算机硬件组成&#xff0c;运算器&#xff0c;控制器 计算机基本硬件系统五大组成部分&#xff1a;运算器&#xff0c;控制器&#xff0c;存储器&#xff0c;I/O设备 运算器的四个重要寄存器&#xff1a; 算术逻辑单元&#xff08;实时对数据的算术和逻辑运算&#xff0c;…

Excel和Word日常使用记录:

Excel使用总结 表格颜色填充&#xff1a; 合并单元格&#xff1a; 选中你要合并的单元格区域。 按下快捷键 Alt H&#xff0c;然后松开这些键。 再按下 M&#xff0c;接着按 C。 这个组合键执行的操作是&#xff1a;Alt H&#xff1a;打开“主页”选项卡。 M&#xff1a;选…

八、适配器模式

适配器模式&#xff08;Adapter Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许不兼容的接口之间进行合作。适配器模式通过创建一个适配器类来转换一个接口的接口&#xff0c;使得原本由于接口不兼容无法一起工作的类可以一起工作。 主要组成部分&#xff1a; 目标…

凸优化学习(1)——什么是凸优化、凸集、凸函数

&#x1f345; 写在前面 &#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;这里是hyk写算法了吗&#xff0c;一枚致力于学习算法和人工智能领域的小菜鸟。 &#x1f50e;个人主页&#xff1a;主页链接&#xff08;欢迎各位大佬光临指导&#xff09; ⭐️近…

springboot广州科技学院后勤综合管理系统---附源码79264

摘要 随着信息技术的快速发展&#xff0c;学院后勤综合管理系统在高校中扮演着越来越重要的角色。本论文旨在设计并实现一种基于SpringBoot框架的学院后勤综合管理系统&#xff0c;以提高学院后勤工作的效率和管理水平。在该论文中&#xff0c;我们将首先介绍学院后勤管理系统的…

828华为云征文|华为云Flexus X实例docker部署最新gitlab社区版,搭建自己的私人代码仓库

828华为云征文&#xff5c;华为云Flexus X实例docker部署最新gitlab社区版&#xff0c;搭建自己的私人代码仓库 华为云最近正在举办828 B2B企业节&#xff0c;Flexus X实例的促销力度非常大&#xff0c;特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Ng…

支持大型程序代码和拥有大型嵌入式SRAM的指纹芯片-P1032BF1

指纹芯片 - P1032BF1是一款基于ARM Cortex-M3的单片机&#xff0c;专为Wi-Fi /蓝牙通信控制而设计&#xff1b;能够实现指纹的图像采集、特征提取、特征比对&#xff0c;可应用于智能锁&#xff1b;支持大型程序代码和拥有大型嵌入式SRAM&#xff0c;也可用于一般的MCU应用。 …

【文档资料】《你缺失的那门计算机课》

# 站长的话 站长认为此书写的非常好&#xff0c;能够很好的GET到当下普通人所遇到的难点&#xff0c;正如此书的序章所写&#xff1a;“据我们观察&#xff0c;许多同学对「电脑」并不熟悉&#xff0c;甚至可以说是陌生&#xff1a;他们可能在网上被下载到各种「P2P 高速下载器…

C语言代码练习(第十八天)

今日练习&#xff1a; 48、猴子吃桃问题。猴子第1天摘下若干个桃子&#xff0c;当即吃了一半&#xff0c;还不过瘾&#xff0c;又多吃了一个。第2天早上又将剩下的桃子吃掉一半&#xff0c;又多吃了一个。以后每天早上都吃了前一天剩下的一半零一个。到第10天早上想再吃时&…

onpm报错: Install failed

api 9 安装ohos/pulltorefresh2.0.1报错误 ohpm install ohos/pulltorefresh2.0.1 ohpm INFO: fetching meta info of package ohos/pulltorefresh ohpm WARN: fetch meta info of package ohos/pulltorefresh failed - GET https://registry.npmjs.org/ohos/pulltorefresh 404…

Git环境搭建

我的博客大纲 我的GIT学习大纲 Git安装步骤&#xff1a; 1.官网地址 查看 GNU 协议&#xff0c;可以直接点击下一步&#xff1a; 2.Git配置选项如下&#xff1a; 3.选择后台客户端连接协议&#xff0c;选默认值 OpenSSL&#xff0c;然后下一步。 4.Git换行符号 5.选择终端类型…

护眼台灯对眼睛好吗?眼科医生推荐的台灯告诉你答案

作为一名家长&#xff0c;我深刻体会到保护孩子眼部健康的重要性。随着科技的迅猛发展&#xff0c;孩子们越来越多地接触并依赖电子设备&#xff0c;如平板电脑、手机和电视&#xff0c;长时间盯着屏幕已成为他们日常生活的一部分。然而&#xff0c;这些屏幕发出的蓝光及闪烁的…

2023年408真题计算机网络篇

https://zhuanlan.zhihu.com/p/6954228062023年网络规划设计师上午真题解析TCP流量计算_哔哩哔哩_bilibili 1 1在下图所示的分组交换网络中&#xff0c;主机H1和H2通过路由器互联&#xff0c;2段链路的数据传输速率为100 Mb/s、时延带宽积 &#xff08;即单向传播时延带宽&am…

Centos7.9部署Gitlab-ce-16.9

一、环境信息 软件/系统名称版本下载地址备注Centos77.9.2009https://mirrors.nju.edu.cn/centos/7.9.2009/isos/x86_64/CentOS-7-x86_64-DVD-2009.isogitlab-cegitlab-ce-16.9.1https://mirror.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/gitlab-ce-16.9.1-ce.0.el7.x86_64.rpm…