前言
上篇我们介绍了链表算法的相关概念，并结合基础题目加以讲解。本篇将通过三道进阶题目，进一步深化对于链表算法的掌握运用。
第一章：重排链表
1.1 题目链接：https://leetcode.cn/problems/reorder-list/description/
1.2 题目分析：
题目所要求的重组即为将后半部分链表逆序，之后逐个加入到前半部分链表中。
1.3 思路讲解：
- 既然后半部分需要逆序，那么我们首先需要找到
中间结点
逆序时直接采用头插法可大大简化步骤
- 查找中间节点时，假设节点总数为奇数个，那么即为正中间的节点
- 若节点总数为偶数个，则可采取靠右的中间节点，该中点的下一个节点开始即为后半部分需要重排的链表
此时3为中间结点，重排结果如下：
1.4 代码实现：
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* newhead=new ListNode(0);//哨兵位
newhead->next=head;
ListNode* slow=head,*fast=head;
//查找中间节点
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
ListNode* cur1=head,*cur2=slow->next;//前后两部分链表头
slow->next=nullptr;//断开两部分链接
//将后半部分链表逆序
ListNode* head2=new ListNode(0);
while(cur2)
{
ListNode* next=cur2->next;
cur2->next=head2->next;
head2->next=cur2;
cur2=next;
}
cur2=head2->next;
ListNode* cur=newhead;
//合并
while(cur1||cur2)
{
if(cur1)
{
cur->next=cur1;
cur=cur1;
cur1=cur1->next;
}
if(cur2)
{
cur->next=cur2;
cur=cur2;
cur2=cur2->next;
}
}
}
};
第二章：合并K个升序链表
2.1 题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/description/
2.2 题目分析：
- 题目给定K个升序链表，要求将其合并为一个总的升序链表
- 必须进行节点的依次修改连接，而非单纯修改值
2.3 思路讲解：
此题的核心在于每一个链表自身已经是升序排列。
- 我们可以采用
优先级队列priority_queue，建立一个小根堆，将各个链表的头节点依次入堆。 - 由于链表为自定义类型，还需要我们定义一个比较函数
- 此时堆内已经按照节点大小依次排列，之后持续出堆进堆即可完成合并排序。
2.4 代码实现：
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
//自定义比较函数
struct cmp
{
bool operator() (const ListNode* l1,const ListNode* l2)
{
return l1->val>l2->val;
}
};
//建立小根堆
priority_queue<ListNode*,vector<ListNode*>,cmp> min;
for(auto e:lists)
{
if(e)
min.push(e);
}
ListNode* newhead=new ListNode(0);
ListNode* cur=newhead;
while(!min.empty())
{
ListNode* newnode=min.top();
min.pop();
if(newnode->next)
min.push(newnode->next);//进出操作
cur->next=newnode;
cur=newnode;//连接
}
return newhead->next;
}
};
第三章：K个一组翻转链表
3.1 题目链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/description/
3.2 题目分析：
- 现给定链表，要求每k个节点进行一次逆序重排
- 剩余不足K的节点按照原顺序链接
- 必须修改节点连接，而非单纯修改节点的值
3.3 思路讲解：
本题的核心操作即为逆序，而逆序我们已经了解了一种极为便捷的方法——头插。
- 我们可以首先计算出需要翻转的次数，若节点个数为n，则翻转次数为n/k。
- 此后进行n/k次翻转并依次连接即可。
3.4 代码实现：
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
int n=0;
ListNode* cur=head;
while(cur)
{
n++;
cur=cur->next;
}//计算节点个数
n/=k;//计算翻转次数
ListNode* newhead=new ListNode(0);
ListNode* prev=newhead;
cur=head;
for(int j=0;j<n;j++)
{
//逆序
ListNode* temp=cur;
for(int i=0;i<k;i++)
{
ListNode* next=cur->next;
cur->next=prev->next;
prev->next=cur;
cur=next;
}
prev=temp;
}
//连接剩余部分
if(cur)
prev->next=cur;
prev=newhead->next;
delete newhead;
return prev;
}
};
第四章：现实世界中的链表——灵活性的代言人
链表不仅是理论的产物，它在实际应用中发挥着不可替代的作用。许多复杂数据结构和算法的基础都源于链表的思想：
LRU缓存
使用双链表实现最近最少使用（LRU）缓存，可以高效地实现插入、删除和访问操作，是操作系统和数据库中广泛应用的算法。
动态内存管理
在操作系统中，链表被用来实现内存分配的自由链表（Free List），以动态追踪可用的内存块。
图与树的表示
图和树的邻接表表示常常依赖链表，以节省存储空间并保持访问灵活性。
第五章：链表的优雅与局限
尽管链表算法有着灵活动态的特性，但它并非完美无瑕。链表的局限性同样值得我们思考：
- 随机访问效率低：由于链表无法像数组那样通过索引直接访问元素，因此查找操作可能需要耗费较多时间。
- 额外存储开销：每个节点都需要存储额外的指针，占用更多内存。
然而，正是这些局限，使链表在适合的场景中更加熠熠生辉。
尾声：链表的哲学——从离散到连贯
链表算法的魅力在于它的灵活与动态，它不仅仅是一个数据结构，更是一种哲学思考——如何将孤立的事物通过简单的连接，构成一片完整的世界。从单链表到双链表，从循环链表到跳跃表，链表的多样性和适应性启发我们：在设计系统与算法时，学会连接、适应与创造，方能构建出优雅而高效的解决方案。
链表，是数据结构的诗篇，它用指针为每一个节点赋予意义，用算法为每一个节点找到归属。或许，这正是计算机科学的浪漫之处。
本篇关于链表算法的讲解就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
