算法思想总结:链表

一、链表的常见技巧总结

二、两数相加

. - 力扣(LeetCode)

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {//利用t来存进位信息int t=0;ListNode*newhead=new ListNode(0);//创建一个哨兵节点,方便尾插ListNode*ptail=newhead;//ptail方便尾插ListNode* cur1=l1,*cur2=l2;while(cur1||cur2||t==1)//t==1防止后面有进位没加上{if(cur1)  {t+=cur1->val; cur1=cur1->next;}if(cur2)  {t+=cur2->val;cur2=cur2->next;}ptail->next=new ListNode(t%10);ptail=ptail->next;t/=10;}ListNode*ret=newhead->next;delete newhead;return ret;}
};

 三、两两交换链表中的节点

 四、重排链表

. - 力扣(LeetCode)

class Solution {
public:void reorderList(ListNode* head) {//方法1,利用一个数据结构将每个节点存起来,通过下标去访问//方法2, (1)利用快慢指针,找中点 (2) 拆开链表 从中点开始往后翻转 (3)进行合并成新链表if(head==nullptr||head->next==nullptr||head->next->next==nullptr) return;ListNode*mid=midnode(head);//找到中间节点//断开链表ListNode*l1=head;ListNode*l2=mid->next;mid->next=nullptr;//然后反转2l2=reverseList(l2);//合并链表mergeList(l1,l2);}ListNode*midnode(ListNode* head){ListNode*fast=head;ListNode*slow=head;while(fast->next!=nullptr&&fast->next->next!=nullptr)//确保后面两步能走{fast=fast->next->next;slow=slow->next;}return slow;//此时慢指针指向的就是最小的节点}ListNode* reverseList(ListNode* head){ListNode*p1=nullptr;ListNode*p2=head;ListNode*p3=head->next;//记录下一个要遍历的点while(p2){p2->next=p1;p1=p2;p2=p3;if(p3) p3=p3->next ;}return p1;}void mergeList(ListNode* l1, ListNode* l2){ListNode* temp1,*temp2;while(l1!=nullptr&&l2!=nullptr){temp1=l1->next;temp2=l2->next;l1->next=l2;l1=temp1;//回到原链表0l2->next=l1;l2=temp2;//回到原链表}}
};

五、合并k个升序链表

. - 力扣(LeetCode)

 优先级队列:

class Solution {
public://建小堆需要greaterstruct greater //构造一个仿函数{bool operator()(const ListNode*l1,const ListNode*l2){return l1->val>l2->val;}};ListNode* mergeKLists(vector<ListNode*>& lists) {//建立优先级队列(小堆),每次将堆顶元素插入进去,然后再删除堆顶元素,插入下个位置priority_queue<ListNode*,vector<ListNode*>,greater> heap;//建立一个小堆//入堆for(auto l:lists) if(l) heap.push(l);//因为有可能里面存的是一个空链表//开始合并k个有序链表ListNode*newnode=new ListNode(0);ListNode*ptail=newnode;//用于帮助我们进行尾插while(!heap.empty()){//进行尾插ListNode*it=heap.top();ptail->next=it;ptail=it;//去到下一个位置准备尾插//删除堆顶元素并将该节点的下一个节点入堆 ,为空就不入heap.pop();if(it->next) heap.push(it->next);}//此时全部的元素都插入完成了,返回最终的链表ListNode*ret=newnode->next;delete newnode;return ret;//时间复杂度o(n*k*logk)}
};

分治思想:

//策略,利用递归解决问题,结合归并排序,合并两个有序链表  (利用分治思想)
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists){int n=lists.size();return merge(lists,0,n-1);//让merge帮助我们完成整个区间的归并}ListNode* merge(vector<ListNode*>& lists,int left,int right){//首先,处理边界情况,如果不存在链表或者是只有一个链表,此时没有必要进行下去if(left>right) return nullptr;if(left==right) return lists[left];//让merge帮助我们归并左右区间int mid=(left+right)>>1;ListNode*l1=merge(lists,left,mid);ListNode*l2=merge(lists,mid+1,right);//然后开始进行合并两个有序链表return mergetwolist(l1,l2);}ListNode*mergetwolist(ListNode*l1,ListNode*l2){//考虑两个链表为空的情况if(l1==nullptr) return l2;if(l2==nullptr) return l1;//此时两个链表必然不为空,开始进行合并ListNode*newhead=new ListNode(0);//哨兵节点ListNode*ptail=newhead;//帮助我们进行尾插ListNode*cur1=l1,*cur2=l2;//两个指针分别指向两个链表while(cur1&&cur2)//当两个都不为空的时候{if(cur1->val<cur2->val) {//此时要尾插cur1ptail->next=cur1;ptail=cur1;//更新到下一个位置cur1=cur1->next;//继续去下一个节点遍历}else{ptail->next=cur2;ptail=cur2;//更新到下一个位置cur2=cur2->next;//继续去下一个节点遍历}}//可能有的链表没有遍历完if(cur1) ptail->next=cur1;if(cur2) ptail->next=cur2;//此时返回到目标的位置ListNode*ret=newhead->next;delete newhead;return ret;}
};

六、k个一组翻转链表

. - 力扣(LeetCode)

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int n=0;//记录总数ListNode*cur=head;while(cur)//统计节点个数,并推测有多少组{cur=cur->next;++n;}n/=k;//看看一共需要几组ListNode*newhead=new ListNode(0);//创建一个哨兵节点ListNode*prev=newhead;//记住被头插的点cur=head;//从head开始进行头插//翻转n组,每组翻转k个for(int i=0;i<n;++i){ListNode*temp=cur;for(int j=0;j<k;++j){//用头插的逻辑ListNode*next=cur->next;;cur->next=prev->next;prev->next=cur;cur=next;//继续去链表的下一个点}prev=temp;//更新prev}//循环结束后,将后面的不需要逆序的部分接上prev->next=cur;ListNode*ret=newhead->next;delete newhead;return ret;}
};

七、旋转链表

. - 力扣(LeetCode)

思路1:截断再连接

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {//让链表成环(闭合成环),然后在指定位置断开if(head==nullptr||head->next==nullptr||k==0) return head;int count=1;//数节点数量ListNode*ptail=head;while(ptail->next!=nullptr) //找到尾节点,并统计节点数{ptail=ptail->next;++count;}int add=count-k%count;//看看具体是翻转几次if(add==count) return head;//避免不需要翻转的情况//截断重连ListNode*cur=head;while(--add) cur=cur->next; //找到被截断的位置ListNode*ret=cur->next;cur->next=nullptr;//断开cur=ret;while(cur->next!=nullptr) cur=cur->next;//找到尾节点cur->next=head;//连接return ret; }
};

思路2:链表成环,指定位置截断

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {//让链表成环,然后在指定位置断开if(head==nullptr||head->next==nullptr||k==0) return head;int count=1;//数节点数量ListNode*ptail=head;while(ptail->next!=nullptr) //找到尾节点,并统计节点数{ptail=ptail->next;++count;}int add=count-k%count;//看看具体是翻转几次ptail->next=head;//头尾相连while(add--) ptail=ptail->next;ListNode*ret=ptail->next;ptail->next=nullptr;return ret; }
};

思路3:逆置前n-k个,再逆置后k个,最后整体逆置

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(head==nullptr||head->next==nullptr||k==0) return head;//先逆置前n-k个,再逆置后k个,再整体逆置int count=1;//数节点数量ListNode*ptail=head;while(ptail->next!=nullptr) //找到尾节点,并统计节点数{ptail=ptail->next;++count;}int add=count-k%count;//看看具体是翻转几次if(add==count) return head;//开始找前n-k个节点ListNode*cur=head;while(--add) cur=cur->next;ListNode*l2=cur->next;//第二个链表cur->next=nullptr;//断开ListNode* l1=reverse(head);l2=reverse(l2);head->next=ptail;//连接起来return reverse(l1);//然后整体翻转}ListNode*reverse(ListNode* head){ //只有一个节点,没什么好逆置的if(head==nullptr||head->next==nullptr) return head;ListNode*p1=nullptr,*p2=head,*p3=head->next;while(p2){p2->next=p1;p1=p2;p2=p3;if(p3) p3=p3->next;}return p1;}
};

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

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

相关文章

基于Docker构建CI/CD工具链(十)总结

我们用九篇文章简单的介绍了使用Docker构建CICD工具链&#xff0c;希望对你的工作有所帮助。 基于Docker构建CI/CD工具链&#xff08;一&#xff09;构建基础工具镜像 基于Docker构建CI/CD工具链&#xff08;二&#xff09;快速搭建Gitlab代码库 基于Docker构建CI/CD工具链&…

RA4000CE为汽车动力传动系统提供解决方案

目前汽车电气化的水平越来越高&#xff0c;其中比较显著的一个发展方向就是将发动机管理系统和自动变速器控制系统&#xff0c;集成为动力传动系统的综合控制(PCM)。作为汽车动力的核心部件&#xff0c;通过电子系统的运用&#xff0c;将外部多个传感器和执行环节的数据进行统一…

第十五届蓝桥杯题解-好数

题目大意&#xff1a;一个数的低位为奇数&#xff0c;次低位为偶数&#xff0c;以此类推的数成为好数&#xff0c;例如&#xff1a;1&#xff0c;3&#xff0c;5&#xff0c;7&#xff0c;9 给定一个n&#xff0c;求1-n所有好数的个数&#xff0c;n<1e7 思路&#xff1a;一…

媒体邀约的好处?怎么邀请媒体?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 媒体邀约的好处主要体现在提高品牌知名度、扩大受众群体以及与媒体建立良好的合作关系。 媒体邀约是一种有效的公关策略&#xff0c;通过吸引媒体关注来促进信息的传播。它可以帮助组织…

速看!DaVinci Resolve Studio19.0 下载地址及安装教程

DaVinci Resolve是一款全面的视频后期制作软件&#xff0c;由Blackmagic Design开发。它集成了视频编辑、颜色校正、音频后期处理和视觉效果合成等功能&#xff0c;被广泛应用于电影、电视和广告制作等领域。 DaVinci Resolve提供了强大的视频编辑工具&#xff0c;用户可以进行…

【智能算法】鸭群算法(DSA)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献 1.背景 2021年&#xff0c;Zhang等人受到自然界鸭群觅食行为启发&#xff0c;提出了鸭群算法&#xff08;Duck Swarm Algorithm, DSA&#xff09;。 2.算法原理 2.1算法思想 DSA基于自然界鸭群觅食过程&…

机器人视觉软件实现目标检测通常借助深度学习技术和计算机视觉算法

机器人视觉软件实现目标检测通常借助深度学习技术和计算机视觉算法。以下是一般而言的目标检测实现步骤&#xff1a; 1、数据收集与标注&#xff1a;首先需要收集包含目标物体的大量图像数据&#xff0c;并对这些图像进行标注&#xff0c;标注出目标物体的位置和类别信息。这些…

数据结构速成--栈

由于是速成专题&#xff0c;因此内容不会十分全面&#xff0c;只会涵盖考试重点&#xff0c;各学校课程要求不同 &#xff0c;大家可以按照考纲复习&#xff0c;不全面的内容&#xff0c;可以看一下小编主页数据结构初阶的内容&#xff0c;找到对应专题详细学习一下。 目录 一…

基于微信小程序投票评选系统的设计与实现(论文+源码)_kaic

摘 要 社会发展日新月异&#xff0c;用计算机应用实现数据管理功能已经算是很完善的了&#xff0c;但是随着移动互联网的到来&#xff0c;处理信息不再受制于地理位置的限制&#xff0c;处理信息及时高效&#xff0c;备受人们的喜爱。所以各大互联网厂商都瞄准移动互联网这个潮…

Vue3(四):组件通信详解(九种方法)

主要有九种方法&#xff0c;以下是详细解释及使用方法&#xff1a; 1.props props实现父子间的通信&#xff0c;是使用频率最高的。 &#xff08;1&#xff09;父传子&#xff1a;属性值是非函数。 以Father.vue和Child.vue 为例。 父组件中&#xff0c;引入子组件并给子组…

实战 K8s ConfigMap:打造动态可配置的云原生应用

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《Kubernetes航线图&#xff1a;从船长到K8s掌舵者》 &#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、前言 1、k8s简介 2、ConfigMap简介 二、Con…

【每日刷题】Day16

【每日刷题】Day16 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; &#x1f33c;文章目录&#x1f33c; 1. 24. 两两交换链表中的节点 - 力扣&#xff08;LeetCode&#xff09; 2. 160. 相交链表 - 力扣&…

xcode c++项目设置运行时参数

在 Xcode 项目中&#xff0c;你可以通过配置 scheme 来指定在运行时传递的参数。以下是在 Xcode 中设置运行时参数的步骤&#xff1a; 打开 Xcode&#xff0c;并打开你的项目。在 Xcode 菜单栏中&#xff0c;选择 "Product" -> "Scheme" -> "E…

一次配置Docker环境的完整记录

一次配置Docker环境的完整记录 Docker环境搭建报错与解决报错一报错二报错三 Docker环境搭建 本节介绍了一次配置docker环境的完整记录&#xff1a; 编写Dockerfile文件&#xff1a; FROM pytorch/pytorch:1.10.0-cuda11.3-cudnn8-develRUN rm /etc/apt/sources.list.d/cuda.l…

LeetCode 409—— 最长回文串

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 要想组成回文串&#xff0c;那么只有最中间的字符可以是奇数个&#xff0c;其余字符都必须是偶数个。 所以&#xff0c;我们先遍历一遍字符串&#xff0c;统计出每个字符出现的次数。 然后如果某个字符出现了偶…

C++string类(个人笔记)

string类 1.认识string的接口以及熟练使用常用接口1.1string类对象的常见构造1.2string类对象的容量操作1.3string类对象的访问及遍历操作1.4string类对象的修改操作 2.vs 和g下string结构的说明3.string类运用的笔试题4.string类的模拟实现 1.认识string的接口以及熟练使用常用…

使用 Docker 部署 SurveyKing 调查问卷系统

1&#xff09;SurveyKing 介绍 SurveyKing 是一款功能强大、操作简便的开源问卷系统。它不仅满足了用户对问卷调查的基本需求&#xff0c;还提供了丰富的逻辑设置和灵活的问题设置&#xff0c;使得问卷制作更加智能化和个性化。此外&#xff0c;SurveyKing 还具有快速部署和安全…

【从浅学到熟知Linux】进程控制下篇=>进程程序替换与简易Shell实现(含替换原理、execve、execvp等接口详解)

&#x1f3e0;关于专栏&#xff1a;Linux的浅学到熟知专栏用于记录Linux系统编程、网络编程等内容。 &#x1f3af;每天努力一点点&#xff0c;技术变化看得见 文章目录 进程程序替换什么是程序替换及其原理替换函数execlexeclpexecleexecvexecvpexecvpeexecve 替换函数总结实现…

深入剖析跨境电商平台风控机制,探索测评安全与稳定的秘诀

在跨境电商测评市场鱼龙混杂的当下&#xff0c;测评过程中可能隐藏的陷阱保持高度警觉。多年的测评经验告诉我们&#xff0c;选择一个适合的测评系统对于项目的成功至关重要。近年来&#xff0c;测评技术如雨后春笋般涌现&#xff0c;市场上涌现出众多测评系统&#xff0c;覆盖…

配置路由器实现互通

1.实验环境 实验用具包括两台路由器(或交换机)&#xff0c;一根双绞线缆&#xff0c;一台PC&#xff0c;一条Console 线缆。 2.需求描述 如图6.14 所示&#xff0c;将两台路由器的F0/0 接口相连&#xff0c;通过一台PC 连接设备的 Console 端口并配置P地址&#xff08;192.1…