链表算法速成计划

embedded/2024/11/24 21:03:02/

链表算法速成计划

1.准备工作

1.1创建链表节点结构体

struct ListNode {int val;ListNode* next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};

1.2 在IDE中创建链表代码

ListNode* createRandomLinkedList(int length)
{if (length <= 0) return NULL;// 设置随机数种子std::random_device rd; // 随机数种子std::mt19937 gen(rd()); // Mersenne Twister 随机数引擎std::uniform_int_distribution<> dis(0, 99); // 随机数分布// 创建头节点，数据为0到99之间的随机值ListNode* head = NULL;// 循环创建其他节点for (int i = 1; i < length; ++i){ListNode* newListNode = new ListNode(dis(gen) % 100);newListNode->next = head;head = newListNode;}return head;
}

1.3 打印链表和释放链表代码

// 打印链表的函数
void printLinkedList(ListNode* head)
{ListNode* current = head;while (current != NULL){std::cout << current->val << " -> ";current = current->next;}std::cout << "NULL" << std::endl;
}

// 释放链表内存的函数
void freeLinkedList(ListNode* head)
{ListNode* current = head;while (current != NULL){ListNode* nextListNode = current->next;delete current;current = nextListNode;}
}

1.4 示例代码

#include <iostream>
#include <random>using namespace  std;
struct ListNode {int val;ListNode* next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode* next) : val(x), next(next) {}
};ListNode* createRandomLinkedList(int length)
{if (length <= 0) return NULL;// 设置随机数种子std::random_device rd; // 随机数种子std::mt19937 gen(rd()); // Mersenne Twister 随机数引擎std::uniform_int_distribution<> dis(0, 99); // 随机数分布// 创建头节点，数据为0到99之间的随机值ListNode* head = NULL;// 循环创建其他节点for (int i = 1; i < length; ++i){ListNode* newListNode = new ListNode(dis(gen) % 100);newListNode->next = head;head = newListNode;}return head;
}// 打印链表的函数
void printLinkedList(ListNode* head)
{ListNode* current = head;while (current != NULL){std::cout << current->val << " -> ";current = current->next;}std::cout << "NULL" << std::endl;
}// 释放链表内存的函数
void freeLinkedList(ListNode* head)
{ListNode* current = head;while (current != NULL){ListNode* nextListNode = current->next;delete current;current = nextListNode;}
}int main() {// 创建链表for (int i = 1; i <= 5; i++){ListNode* head = createRandomLinkedList(10);cout << "第" << i << "次样例:";printLinkedList(head);//本区域填写你的函数！！！！//ListNode* newhead = 你的函数(head);cout << "第" << i << "次结果:";printLinkedList(head);// 释放链表内存freeLinkedList(head);}return 0;
}

在这里插入图片描述

2. 基本操作（必须熟练默写！）

2.1 头插

ListNode* head_insert(ListNode* head, ListNode* node) //head为链表，ListNode为待插入节点
{//本代码正常head为NULL，也就是空链表node->next = head; //ListNode指向headhead = node; //让ListNode作为新的头return head;
}

示例

int main() {ListNode* head = NULL;for (int i = 1; i <= 5; i++){ListNode* newhead = new Node(i);head = head_insert(head, newhead);cout << "第" << i << "次插入结果:";printLinkedList(head);}return 0;
}

在这里插入图片描述

2.2 头删

ListNode* head_delete(ListNode* head) //head为链表
{if (head == NULL)return head; //为空就直接返回ListNode* cur = head; //记录待删除节点head = head->next; //头结点只想下一个free(cur); //释放cur结点return head;
}

示例

int main() {ListNode* head = NULL;for (int i = 1; i <= 5; i++){Node* newhead = new Node(i);head = head_insert(head, newhead);cout << "第" << i << "次插入结果:";printLinkedList(head);}for (int i = 1; i <= 5; i++){head = head_delete(head);cout << "第" << i << "次删除结果:";printLinkedList(head);}return 0;
}

在这里插入图片描述

2.3 中间节点插入（包括尾插）

ListNode* middle_insert(ListNode* head, int val, ListNode* node) //本代码理解意思即可，也就是说先查找到val值的节点，然后在其后面插入ListNode，尾插也可以用这个思想！
{ListNode* pre = head; //pre指插入位置的前一个节点也就是val值的节点while (pre){if (pre->val != val) //如果没有找到val就继续找pre = pre->next;else //找到val后进行插入{node->next = pre->next;pre->next = node;break; //插入后退出循环}}return head; //返回链表头节点
}

示例

int main() {ListNode* head = NULL;for (int i = 1; i <= 5; i++){ListNode* newhead = new ListNode(i);head = head_insert(head, newhead);cout << "第" << i << "次插入结果:";printLinkedList(head);}//在1后面插入10ListNode* newhead = new Node(10);middle_insert(head, 1, newhead);cout << "插入结果:";printLinkedList(head);//在5后面插入20newhead = new Node(20);middle_insert(head, 5, newhead);cout << "插入结果:";printLinkedList(head);return 0;
}

在这里插入图片描述

2.4 删除中间节点（包括尾删）

ListNode* middle_delete(ListNode* head, int val) //先查找到val对应的节点，然后删除该节点
{ListNode* pre = NULL; //pre是需要删除节点的前一个位置，注意：在删除节点中前一个位置很重要，因为你只有通过前一个结点才能将链表连接起来！if (head->val != val) //如果需要删除的是第一个节点，那么他没有前一个节点，所以你得判断一下，如果删除的不是第一个节点，那么就可以将head赋值给pre，然后进行查找{pre = head;}else //如果要删除的是第一个节点也就是头删！{head = head_delete(head);return head;}while (pre->next) //pre->next就是我们要查找的待删除节点，所以这个一定不是NULL的，故while条件是这个{if (pre->next->val != val) //如果不等就往下一个查找{pre = pre->next;}else //如果查到{ListNode* cur = pre->next; //记录待删除节点pre->next = cur->next; //连接前后节点free(cur);break;}}return head;
}

示例

int main() {ListNode* head = NULL;for (int i = 1; i <= 5; i++){ListNode* newhead = new ListNode(i);head = head_insert(head, newhead);cout << "第" << i << "次插入结果:";printLinkedList(head);}head = middle_delete(head,4);cout << "删除4后结果:";printLinkedList(head);head = middle_delete(head, 5);cout << "删除5后（也就是删除第一个位置）结果:";printLinkedList(head);head = middle_delete(head, 1);cout << "删除1后（也就是删除最后个位置）结果:";printLinkedList(head);return 0;
}

在这里插入图片描述

3. 力扣代码练习

3.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 {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newhead=new ListNode(-1);//创建哨兵头节点ListNode* tail=newhead;//永远指向新链表的尾部的节点while(list1&&list2){if(list1->val<list2->val)//如果list1头节点小就让list1头节点尾插到newhead{ListNode* cur=list1;//cur是指向该头节点list1=list1->next;//然后list1就指向他的下一个节点，也就是丢弃了之前的头节点tail->next=cur;//newhead尾节点指向cur节点tail=tail->next;//tail更新到下一个节点}else{//同上ListNode* cur=list2;list2=list2->next;tail->next=cur;tail=tail->next;}}if(list1!=nullptr)//到这一步就是会出现要么list1还剩余节点，list2没有，要么list2还剩余节点，list1没有，这个时候只需要将整条链接到newhead尾巴后面{tail->next=list1;}if(list2!=nullptr){tail->next=list2;}return newhead->next;//返回头节点（要范围next，应为newhead是哨兵）}
};

3.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* deleteDuplicates(ListNode* head) {ListNode* pre=head;//pre指向要删除节点的前一个位置，也就是说pre是指第一个出现该数字的节点，之前后的相同节点都要被删除while(pre&&pre->next)//这里也要保证pre->next不是空，因为可能pre是最后一个节点，那么就没有意义了，也就是说这个循环条件是运行到倒数第二个节点{if(pre->val==pre->next->val)//如果相等这删除这个节点，然后继续循环{//ListNode* cur=pre->next;pre->next=pre->next->next;//free(cur);//考试的时候需要这样写，也就是要释放结点，但是OJ不给你释放所以我就屏蔽掉这两行代码！}else//如果不相等就pre指向下一个节点，  如果不懂自己根据样例画图看看{pre=pre->next;}}return head;}
};

3.3 环形链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {//本题需要特殊技巧：快慢指针ListNode*fast=head;ListNode*slow=head;while(fast&&fast->next)//这里的判断条件是防止fast走到NULL，出现空指针异常  因为fast每次要走两步，所以要保证fast可以走到第二步，也就是说fast和fast->next都不能为空{fast=fast->next->next;//fast走两步slow=slow->next;//slow走一步if(fast==slow)return true;//如果是循环链表，那么fast一定会追上slow，然后就返回true}return false;//走到这一步是因为head不是循环链表，fast走到尾巴了，故跳出循环}
};

3.4 移除链表元素

/*** 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* removeElements(ListNode* head, int val) {ListNode* newhead=new ListNode(-1);//创建一个哨兵，处理特殊情况（删除第一个也就是头删要特殊处理比较麻烦）newhead->next=head;ListNode* pre=newhead;//需要删除节点的前一个while(pre&&pre->next)//pre->next是可能需要删除的结点，故他一定要存在{if(pre->next->val==val)//如果pre->next和val相同则要删除该节点{pre->next=pre->next->next;}else//否则pre往下遍历{pre=pre->next;}}return newhead->next;}
};

3.5 反转链表

class Solution {
public:ListNode* reverseList(ListNode* head) {//头插的应用ListNode* newhead=NULL;while(head){ListNode* cur=head;//记录需要头插的结点head=head->next;//head往下遍历cur->next=newhead;//cur指向头插链表的头newhead=cur;//cur作为 新 头插链表的头节点}return newhead;}
};

3.6 链表的中间结点

class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode* slow=head;ListNode* fast=head;while(fast&&fast->next)//查找链表中间节点，快指针走到结束，慢指针正好到中间{fast=fast->next->next;slow=slow->next;}return slow;}
};

3.7 回文链表

class Solution {
public:bool isPalindrome(ListNode* head) {//算法思路：找到中间节点，将后面一半反转，然后对比ListNode* fast=head;ListNode* slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}//这个时候slow应该是中间节点//但是这个时候有两个情况//1. A->B->C  链表长度为奇数时 fast不为空，slow是中间那个节点//2. A->B->C->D 链表偶数时,fast为空，slow是中间元素上取整，也就是C//所以这里要分情况if(fast){slow=slow->next;//这里对应第一种情况，让slow到下一个节点，这样就可以让两种情况的判断过程一样}//反转链表:模板，本质就是头插 理解背上ListNode* newhead=NULL;while(slow){ListNode* cur=slow;slow=slow->next;cur->next=newhead;//头插newhead=next;}while(newhead)//这样就得到两个链表，head和newhead，但是这里newhead肯定是后面半部分，所以我们使用newhead为空来判断是否结束，每次都判断对应节点是否相等，不相等就不是回文串，相等就都往下一个遍历，直到遍历结束那就是回文串{if(newhead->val!=head->val){return false;}newhead=newhead->next;head=head->next;}return true;}
};

3.8 删除链表的倒数第 N 个结点

    ListNode* removeNthFromEnd(ListNode* head, int n) {//算法思想：让cur先走n个节点，然后让pre从头开始和cur一起走，cur走到结束了，那么pre就走到要删除节点的前一个（题目翻译就是说让pre少走n个节点）// 分析样例：1->2->3->4->5->NULL n=2，也就是说我们要删除4，那么我们要找到3这个位置（也就是5-2=3这个位置，那么我们只需要走两次就可以走到3），我们让cur先走2次，然后让pre和cur一起走，一直让cur走到最后一个节点的时候，pre就是要删除节点的前一个位置ListNode* cur=head;for(int i=0;i<n;i++){if(cur==NULL)//这个是用来判断n是否合理的，比如说我长度一个是4个，你n给我5那我在遍历head的时候就会出现cur走到结束了，这个时候就什么不要操作直接返回headreturn head;cur=cur->next;}if(cur==NULL) return head->next;//这里如果cur走到了尾巴，那么就相当于头插，我们只需要返回头的下一个节点，还是以：1->2->3->4->5->NULL n=5为例，这个时候cur从头5个节点那么就会跑到尾巴，那么这个时候相当于头删//删除算法中头删和中间删除（尾删）要分别处理，我给你的代码模板中也说了ListNode* pre=head;while(cur->next)//cur走到后一个节点{cur=cur->next;pre=pre->next;}pre->next=pre->next->next;//删除中间的结点方法return head;}
};

3.9 排序链表（本题OJ需要nlogn，但是我们考试写出n^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* sortList(ListNode* head) {//对链表进行排序，使用插入排序思想ListNode* newhead=NULL;//排序后的头结点while(head){ListNode* cur=head;//将要插入到新链表的结点head=head->next;//原来链表头结点到下一个if(newhead==NULL||cur->val<newhead->val)//如果一开始为空，或者cur比第一个新链表头结点小，那么只能头插{cur->next=newhead;newhead=cur;}else{ListNode *pre=newhead;//指向将要插入位置的前一个节点while(pre){if(pre->next==NULL||cur->val<pre->next->val)//pre->next==null是查找到尾巴了，只能插入到最后一个位置，cur->val<pre->next->val是cur比pre->next节点值小，所以就要插入到pre结点后面// 比如插入1   插入到-1->0->1->2->3  那么根据插入排序思想就是要插入到第一个比自己大的结点前面{cur->next=pre->next;pre->next=cur;break;//插入成功就跳出循环}pre=pre->next;//否则pre就一直往后查找}}}return newhead;//返回新链表头结点}
};

http://www.ppmy.cn/embedded/140206.html

相关文章

在有网络连接的机器上打包 electron 及其依赖项，在没有网络连接的机器上安装这些离线包

在有网络连接的机器上打包 electron 及其依赖项，在没有网络连接的机器上安装这些离线包

好的&#xff0c;下面是完整的安装语句&#xff0c;分为两部分&#xff1a;在有网络连接的机器上打包 electron 及其依赖项&#xff0c;在没有网络连接的机器上安装这些离线包。 在有网络连接的机器上打包 electron 及其依赖项 # 创建一个目录来存放离线包 mkdir offline-pac…
阅读更多...
Python设计模式详解之5 —— 原型模式

Python设计模式详解之5 —— 原型模式

Prototype 设计模式是一种创建型设计模式&#xff0c;它通过复制已有的实例来创建新对象&#xff0c;而不是通过从头实例化。这种模式非常适合对象的创建成本较高或者需要避免复杂的构造过程时使用。Prototype 模式提供了一种通过克隆来快速创建对象的方式。 1. Prototype 模式…
阅读更多...
【python系列】python数据类型之字典

【python系列】python数据类型之字典

掌握 Python 字典&#xff08;Dictionary&#xff09;数据类型 Python 中的字典&#xff08;Dictionary&#xff09;是一种非常重要的数据结构&#xff0c;用于存储键值对。它类似于现实生活中的字典&#xff0c;允许快速查找对应的值。本文将详细介绍字典的定义、常用操作及其…
阅读更多...
大数据技术之SparkCore

大数据技术之SparkCore

RDD概述 什么是RDD RDD&#xff08;Resilient Distributed Dataset&#xff09;叫做弹性分布式数据集&#xff0c;是Spark中最基本的数据抽象。代码中是一个抽象类&#xff0c;它代表一个弹性的、不可变、可分区、里面的元素可并行计算的集合。 RDD五大特性 RDD编程 RDD的创…
阅读更多...
C#(12) 内部类和分部类

C#(12) 内部类和分部类

前言 我们发现&#xff0c;其实我们这几节一直都在学习拓展相关的方法&#xff0c;不管是拓展方法&#xff0c;还是运算符重载&#xff0c;还是今天的内部类和分部类。它们都可以用来增强、扩展或重新定义类的功能&#xff0c;使得代码更加灵活和可重用。 研究分部类和内部类…
阅读更多...
DTH11传感器温度湿度+esp8266+阿里云+小程序

DTH11传感器温度湿度+esp8266+阿里云+小程序

arduino在之前灯的基础上再添加两个库 Adafruit_Sensor&#xff0c;#include “DHT.h” 代码如下 #include <ESP8266WiFi.h> // 引入Arduino ESP8266核心库 #include <ArduinoJson.h> // 引入JSON处理库 #include <Ticker.h> // 引入定时库 #inclu…
阅读更多...
SciPy库spatial.transform模块Rotation类的from_rotvec 函数介绍

SciPy库spatial.transform模块Rotation类的from_rotvec 函数介绍

SciPy 库的 spatial.transform 模块 Rotation 类 是一个工具类&#xff0c;用于在多种旋转表示形式&#xff08;例如旋转矩阵、四元数、旋转向量、欧拉角等&#xff09;之间进行转换&#xff0c;以及执行旋转操作。 示例代码 1. 构造旋转对象 from scipy.spatial.transform …
阅读更多...
深度学习day1-Tensor 1

深度学习day1-Tensor 1

深度学习 一 初识Torch 1基础介绍 PyTorch是一个基于Python的深度学习框架&#xff0c;最初由Facebook开发&#xff0c;广泛用于计算机视觉、自然语言处理、语音识别等领域。用张量&#xff08;tensor&#xff09;来表示数据&#xff0c;可以在GPU上加速&#xff0c;处理大规…
阅读更多...
最新文章

Copyright @ 2022~2023