数据结构第一章-链表
第一章：链表
链表的测试文件其实不需要太复杂，随便就写一个abcde五个节点就行，主要看能不能跑，你自己的测试输入肯定没有人家leetcode玩的花，交给leetcode测试就好
为什么会有这一系列文章：
虽然本站是2025年才搭建完，但是这一系列笔记是我刚上大学时候用obsidian记的笔记，当时还并没有图床，项目文件全部保存在本地，因此也用了许多obsidian里面的特性（比markdown和latex混用，还有莫名奇妙的跳转其实这个跳转的功能挺好使，待我研究研究怎么在halo上实现跳转到固定章节的功能） 因此有一些只有obsidian里面才有的特性，部分文章的部分如果看的不是很清楚的话还是请各位大脑渲染一下，鞠躬
推荐算法竞赛网站：USACO Training Gateway 给初高中做的
链表逆序
#easy
主要为单链表数据结构
主要思路
一次遍历链表节点，每次遍历一个节点即逆置一个节点
同时不要忘记备份
解决方法如下
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* head1 = head;//指向老的头节点指针
struct ListNode* new_head = NULL;//建立新的头节点指针
while(head1!= NULL)
{
struct ListNode* temp = head1->next;//给原先的节点的下一个节点进行备份
head1->next =new_head;//交换次序
new_head = head1;//移动新节点至原先节点处
head1 = temp;//移动老节点
}
return new_head;//返回的是新的头节点
}
链表逆序PLUS
#medium
这下从之前的全部逆序变成部分的逆序
关键是找到4个节点
注意如果m = 1的话头节点就被改变，返回的头节点就不应该是最开始的头节点，最好的办法是建立一个result根据结果来判断result的值
解决方法如下
struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
int revers_len = right - left +1;//计算要被逆序的数值
struct ListNode* pre_head = NULL;//被逆序之前的指针
struct ListNode * result = head;//返回的结果指针，默认是head
while(head&&--left){ //把指针控制到被逆序的附近
pre_head = head;
head = head->next;
}
struct ListNode* revers_tail = head;//指向被逆序的第一个指针，也是逆序完成之后的最后一个指针
struct ListNode* new_head = NULL;//参考上一题的逆序
while(head&&revers_len){
struct ListNode* temp = head->next;
head->next = new_head;
new_head = head;
head = temp;
revers_len--;
}
revers_tail->next = head;//再逆序完成之后，head指针并不是刚好停留再完成的最后一个指针，而是最后一个的下一个，因为最后一次循环head还会往前走
if(pre_head){//如果指针为空说明是从头开始逆序的
pre_head->next = new_head;//正常连接，此时result就是head
}
else{
result = new_head;//result直接等于new_head
}
return result;
}
求链表交点
#easy
这道题有两个方法，其中一个方法简单但是时间复杂度和空间复杂度都高
方法1
使用set容器 #set的相关知识
set容器只在C++语言里面有
set容器的相关知识
set.find()返回一个迭代器，如果没有再里面找到对应元素的话则返回的迭代器指向set的最后一个元素
所以思路1的方法就出来了
解决办法如下
class Solution {
public:
ListNode getIntersectionNode(ListNode headA, ListNode *headB) {
std::set<ListNode*> node_set;//设置查找集合node_set
while(headA){
node_set.insert(headA);//把headA的每一个元素都插入node_set
headA = headA->next;//遍历链表A
}
while(headB){
if(node_set.find(headB)!=node_set.end())//当在node_set里面找到第一个出现在node_set里面的节点的时候
{
return headB;
}
headB = headB->next;//遍历链表B
}
return NULL;
}
};
方法2
由于set的时间复杂度是nlogn 空间复杂度是n
主要原因是我不会C++
这就有了第二个方法
思路如下
也就是说先找到长的链表，然后移动指针让两个链表一样长即可
BTW这个是_C语言_
代码如下
struct ListNode getIntersectionNode(struct ListNode headA, struct ListNode *headB) {
int len_a = get_list_lenth(headA);
int len_b = get_list_lenth(headB);
if(len_a>len_b){//如果A比B长就前移A
headA = forword_longlist(len_a,len_b,headA);
}
else{//反之亦然
headB = forword_longlist(len_b,len_a,headB);
}
while(headA&&headB){//同时遍历两个链表
if(headA==headB){
return headA;//当相等的时候返回相同的链表
}
headA= headA->next;
headB = headB->next;
}
return NULL;//全部遍历完成之后返回空
}
int get_list_lenth(struct ListNode*head);
int get_list_lenth(struct ListNode*head)//得到链表的长度，你应该看得懂
{
int len = 0;
struct ListNode* p = head;
while(p){
len++;
p = p->next;
}
return len;
}
struct ListNode forword_longlist(int long_len,int short_len,struct ListNode head);
struct ListNode forword_longlist(int long_len,int short_len,struct ListNode head)//把长链表的头节点前移
{
int delta = long_len-short_len;
while(head&&delta){
head = head->next;
delta--;
}
return head;//返回链表位置
}
链表求环
#medium
BTW这道题是链表求环的简化版141. 环形链表 - 力扣（LeetCode）
方法1
同样是用set容器 我同样不会C++
BTW保存的是地址而不是数据域别忘了
解决办法如下
class Solution {
public:
ListNode detectCycle(ListNode head) {
std :: set <ListNode*> node_set; //设置node_set
while(head){
if(node_set.find(head)!= node_set.end()){
return head;//返回环的第一个节点
}
node_set.insert(head);//节点数据全部插入node_set
head = head->next;
}
return NULL;//没有遇到环就返回NULL
}
};
方法2
方法二的空间和时间复杂度都低于方法1，而且不用C++
[[链表，栈，队列，堆的补充内容#快慢指针求环条件分析|代码优化]]
下面是思路
通过计算发现绿色区域和黄色区域长度永远相等
BTW这道题对NO.141来说只要相遇就可以说是有环存在了
- 在这个时候，只需要让两个指针分别从head和meet同时出发就能在环的起点相遇
解决方法如下
struct ListNode detectCycle(struct ListNode head) {
struct ListNode* fast = head ;
struct ListNode* slow = head;//快慢指针
struct ListNode * meet = NULL; //相遇的指针，初始化为空
while(fast){//链表无环且节点为偶数个，这里跳出循环
slow = slow->next;//slow 和fast都先各走一部
fast = fast->next;
if(!fast)//链表无环，且节点个数为奇数个，这里返回
{
return NULL;
}
fast = fast->next;//快指针再走一步
if(fast == slow)
{
meet = slow;//把相遇的meet指针定义到slow或者fast上
break;
}
}
if(meet == NULL){
return NULL;
}
while(head&&meet){
if(head == meet){//如果两个指针相遇
return head;
}
head=head->next;
meet = meet->next;
}
return NULL;
}
这里是分割线,然后是下节课
链表划分
#medium
已知链表头的head与数值X，将所有小于X的节点放在大于或者等于X的节点前
思路：巧用临时头节点
相当于把大于的放在一个链表，小于的放在一个链表，然后再连一起
解决方法如下
struct ListNode* partition(struct ListNode* head, int x){
struct ListNode less_head = {0,NULL};
struct ListNode more_head = {0,NULL};//设置两个临时头节点
struct ListNode* less_ptr = &less_head;
struct ListNode* more_ptr = &more_head;//设立临时指针
while(head){
if(head->val<x){//如果节点小于x，则改节点插入less_ptr后
less_ptr->next = head;
less_ptr = head;
}
else
{//否则插入到more_ptr后面
more_ptr->next = head;
more_ptr =head;
}
head = head->next; //遍历链表
}
less_ptr->next = more_head.next;//less表尾部与more的头部相连
more_ptr->next = NULL;//置空尾部节点指针
return less_head.next;
}
复杂的链表的深度拷贝
#hard
138. 复制带随机指针的链表 - 力扣（LeetCode）
已知一个复杂的链表，节点中有一个指向本链表任意某个
节点的随机指针，也可以为空，求这个链表的深度拷贝
哎呀就是除了next指针之外还有一个random在这里瞎几把乱指
- 深度拷贝：构造生成一个完全新的链表，即使原链表损毁，新链表仍可独立使用
需要用到的知识 #STLmap的使用 又tmd是C++
映射
地址
vector的使用 #vector的使用
vector 是 C++的一个顺序容器，它可以存储任意类型的动态数组。（包括链表）
push_back()：在 vector 的末尾添加一个元素。
. pop_back()：删除 vector 末尾的元素。
insert()：在 vector 的指定位置插入一个或多个元素。
erase()：删除 vector 中的一个或多个元素。
new 是 C++ 中用于动态分配内存的运算符。它会在堆上分配一块内存，大小为指定类型的大小，并返回一个指向该内存块的指针。
std::vector<Node*> node_vec; 这句话就相当于定义了一个里面都是Node * 的空间
node_vec.push_back(new Node(ptr->val)) 这句话就相当于在vector末尾开辟一个Node的节点，里面的val被初始化为ptr->val
map可以将一个元素的值映射为另一个元素的值
在这个例子里面，我们将节点的地址映射为节点的位置，这样我们可以通过节点的地址来找到对应节点的位置
通过这个方法，我们可以得到以下思路：
解决思路如下
class Solution {
public:
Node* copyRandomList(Node* head) {
std::map<Node* ,int> node_map;//地址到节点的map
std::vector<Node*> node_vec; //使用vector来储存节点位置访问地址
Node* ptr = head;
int i = 0;
while(ptr){//将新链表节点push进入node_vec生成了对应新链表节点位置到地址的map
node_vec.push_back(new Node(ptr->val));
node_map[ptr] = i;
ptr = ptr->next;//遍历原始列表
i++;
}//i记录节点位置
node_vec.push_back(0);
ptr = head;
i = 0; //再次遍历原始链表，链接新链表的next指针,random指针
while(ptr){
node_vec[i]->next = node_vec[i+1];
if(ptr->random){//当random指针不空时
int id = node_map[ptr->random];//根据node_map确认
node_vec[i]->random = node_vec[id];
}
ptr = ptr->next;//链接新链表至random指针
i++;
}
return node_vec[0];
}
};
排序链表的合并（上）
#easy
已知两个_已排序链表头节点指针l1和l2，将两个链表合并，合并后依然有序_ 返回合并后的头节点
思路
解决方法如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode temp_head = {0};//设置临时头节点
struct ListNode *pre = &temp_head;//使用pre指针
while(list1&&list2){//l1和l2不空的时候进行比较
if(list1->val < list2->val){//将pre与较小的节点进行连接
pre->next = list1;
list1 = list1->next;
}
else
{
pre->next = list2;
list2 = list2->next;
}
pre=pre->next;//pre指向新连接的节点
}
if(list1){//如果l1有剩余
pre->next = list1 ;//l1接到pre后
}
if(list2){
pre->next = list2;
}
return temp_head.next;
}
排序链表的合并（下）
#hard
从两个变成k个
传入的是所有链表头节点的vector ListNode* mergeKlists(std::vector<ListNode*> &lists)
方法1——暴力合并
不用看了，绝壁超时
方法2——先排序后相连
注意sort函数需要一个判断函数
方法2的解决办法
bool cmp(const ListNode*a,const ListNode*b){
return a->val < b->val;
}
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
std::vector<ListNode*>node_vec;
for(int i =0;i<lists.size();i++){
ListNode* head = lists[i]; //遍历k个链表，将节点全部添加至Node_vec
while(head){
node_vec.push_back(head);
head = head->next;
}
}
if(node_vec.size() == 0){
return NULL; //根据节点数值进行排序
}
std::sort(node_vec.begin(),node_vec.end(),cmp);
for(int i = 1;i<node_vec.size();i++){
//连接新的链表
node_vec[i-1]->next = node_vec[i];
}
node_vec[node_vec.size()-1]->next = NULL;
return node_vec[0];
}
};
其node_vec.size()返回的是node_vec里面节点的数量
值得一提的是，在这一段代码里面，sort函数会把里面所有的节点进行整体排序，但不会改变连接关系举个例子，假设有两个链表，第一个链表为 1->4->5，第二个链表为 2->3->6。在将这两个链表中的所有节点添加到 node_vec 向量后node_vec 的内容为 [1, 4, 5, 2, 3, 6]。
用 std::sort(node_vec.begin(),node_vec.end(),cmp); 对 node_vec 进行排序。排序后node_vec 的内容变为 [1, 2, 3, 4, 5, 6]。但是，这并不会改变原来两个链表中节点之间的连接关系。也就是说，第一个链表仍然是 1->4->5，第二个链表仍然是 2->3->6。
方法3——分治后相连 #分治思想
详解在[[第四章：递归，回溯和分治#分治算法的归并排序|分治算法]]
最优的算法
方法3的解决办法
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0){
return NULL ; //如果lists为空，则返回NULL
}
if(lists.size() == 1){
return lists[0];
}
if(lists.size() == 2){//如果只有两个list，调用两个list merge函数
return mergeTwoLists(lists[0],lists[1]);
}
int mid = lists.size()/2;
std::vector<ListNode*>sub1_lists;//拆分为两个子lists
std::vector<ListNode*>sub2_lists;
for(int i =0;i<mid;i++){
sub1_lists.push_back(lists[i]);
}
for(int i =mid;i<lists.size();i++){
sub2_lists.push_back(lists[i]);
}
ListNode* l1 = mergeKLists(sub1_lists);
ListNode* l2 = mergeKLists(sub2_lists);
return mergeTwoLists(l1,l2);//分治处理
}
};
关于其中mergeTwolists函数参考[[第一章：链表#排序链表的合并（上）|双有序链表合并]]
实际上分治的思想就是把大问题拆分成小问题，然后用递归的思想来把小问题的结果加起来
好耶，下课了
