文章目录
前言
数据结构的诗篇
在计算机科学的浩瀚宇宙中，链表（Linked List）是一颗璀璨的星辰。它不像数组那样以整齐的阵列横亘在内存中，而是以一种灵活、优雅的方式连接彼此，就如同一首散文诗，将离散的节点串联成一段连绵的故事。链表算法，以其独特的动态性和简洁之美，成为数据结构中不可或缺的一部分。本文将带您深入链表的世界，探索其核心思想、操作技巧以及实际应用。
第一章：链表的意境——节点的孤岛与连接的艺术
每一个数据，仿佛是孤独的岛屿，然而链表却为它们架起了桥梁。链表（Linked List）的精髓在于“连接”：它通过指针或引用，将彼此孤立的节点串联成一条灵活的数据链条。链表结构不仅是一种存储数据的工具，更是一种动态存储的哲学。它让每一个节点都与另一个产生牵绊，共同构成一个有机的整体。
链表的种类如画中风景：
- 单链表：单向延伸的步伐，宛如小径通幽。
- 双链表：前后兼顾的连接，如时光流转的轨迹。
- 循环链表：首尾相连的结构，仿若永恒的轮回。
在这些结构中，链表的灵活性和动态性显露无疑：不必固定内存的长度，可以在运行时添加、删除，甚至随心调整。这种动态特性正是链表算法的灵魂。
第二章：链表算法的流动美学
链表算法，如溪流般灵动，轻柔地解决复杂问题。无论是节点的插入与删除，还是遍历与反转，它们都以一种优雅的方式诠释了灵活存储的真谛。
遍历链表：追逐节点的足迹
遍历是链表算法的基础。我们从起始节点出发，顺着指针一路向前，直至抵达终点。代码中，遍历就像一次穿越数据森林的漫步：
Node* current = head;
while (current != nullptr) {
cout << current->data << " ";
current = current->next;
}
插入与删除：重新定义节点的关系
在链表中，节点的插入与删除尤为灵活——无需像数组那样移动大量数据，只需调整指针便可完成。以单链表为例，插入操作如下：
Node* newNode = new Node(val);
newNode->next = current->next;
current->next = newNode;
链表反转：逆流而上的力量
链表反转是一种经典的操作，既考验逻辑，又蕴含哲理。我们将节点的指针方向反转，仿佛让时间倒流，路径重新定义：
Node* prev = nullptr;
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
current->next = prev;
prev = current;
current = next;
}
head = prev;
下面我们将结合具体题目加以讲解实现。
第三章：两数相加
3.1 题目链接：https://leetcode.cn/problems/add-two-numbers/description/
3.2 题目分析：
- 现有两非空链表，每一个节点存储一个非负整数，且连接方式为逆序
- 要求返回相同形式的链表，其每一个节点所存储的值为两链表对应节点的和
3.3 思路讲解：
由于要求返回的是链表的头节点，而非要求返回相加之和，因此我们只需要将两链表的各个节点逐次相加即可，无需进行逆序操作。
注意：
在解答链表类算法题时，常常需要创建
哨兵位，以及next，prev，cur等指针来方便我们操作，此时无需担心空间的消耗。
具体操作如下：
- 令cur1=l1,cu2=l2，t表示进位，newhead表示哨兵位
- 逐个遍历两个链表的每一个节点相加，并进行新节点的创建和连接
- 两个链表的长度可能一长一短，因此需注意遍历循环条件
3.4 代码实现：
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* newhead=new ListNode(0);//哨兵位
ListNode* cur1=l1;
ListNode* cur2=l2;
ListNode* cur=newhead;
int t=0;//计算进位
while(cur1||cur2||t)
{
//两链表节点相加
if(cur1)
{
t+=cur1->val;
cur1=cur1->next;
}
if(cur2)
{
t+=cur2->val;
cur2=cur2->next;
}
ListNode* newnode=new ListNode(t%10);
cur->next=newnode;
cur=newnode;
t=t/10;//更新t的值
//创建新节点及连接
}
return newhead->next;
}
};
第四章：两两交换链表中的节点
4.1 题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
4.2 题目分析：
- 给定链表，两两交换相邻节点
- 需要交换节点，而非单纯修改节点的值
- 如果为奇数个节点，最后一个节点无需交换
4.3 思路讲解：
题目的核心操作就是交换两个节点，此处可以通过定义prev,cur,next指针和哨兵位的方式简化操作。
图中红线标记部分即为所需改变的指针。
交换结果如下：
4.4 代码实现
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
} // 处理特殊情况
ListNode* newhead = new ListNode(0); // 哨兵位
ListNode* prev = newhead;
ListNode* cur = head;
ListNode* next = head->next;
ListNode* nnext = next->next;
ListNode* temp = head;
int n = 0;
while (temp) {
n++;
temp = temp->next;
}
n /= 2; // 需要执行交换的次数
while (n--) {
// 交换操作
prev->next = next;
cur->next = next->next;
next->next = cur;
// 更新操作
if (nnext) {
prev = cur;
cur = nnext;
}
if (cur) {
next = cur->next;
}
if (next) {
nnext = next->next;
}
}
return newhead->next;
}
};
小结
本篇关于链表算法的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
