第二章 线性表
2.2 链表
链表解决了数组在内存中不能连续存放的问题。 链表的时间复杂度：查找 O(n); 删除，插入（头插或尾插）是 O(1)；
C++算法
C++ 数据结构与算法：线性表之链表
介绍 C++ 链表的数据结构与实现，包括头插尾插、查找删除等操作。分析了链表内存占用与访问效率的优缺点。结合 LeetCode 经典题目，演示了反转链表、删除倒数第 N 个节点、合并有序链表、检测环、求交点及节点交换等算法，重点讲解双指针与快慢指针的应用场景及时间复杂度。
介绍 C++ 链表的数据结构与实现，包括头插尾插、查找删除等操作。分析了链表内存占用与访问效率的优缺点。结合 LeetCode 经典题目，演示了反转链表、删除倒数第 N 个节点、合并有序链表、检测环、求交点及节点交换等算法，重点讲解双指针与快慢指针的应用场景及时间复杂度。
链表解决了数组在内存中不能连续存放的问题。 链表的时间复杂度：查找 O(n); 删除，插入（头插或尾插）是 O(1)；
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
实现一个链表，支持头插入，尾查，查找元素，删除元素，删除所有 value 的元素，打印链表。
// 支持头插入，尾查，查找元素，删除元素，删除所有 value 的元素，反转链表，打印链表
class LinkList {
public:
LinkList() : m_pHead(new Node(-1)), m_pTailNode(m_pHead) {}
~LinkList() {
// 释放所有链表
Node* p = m_pHead->next;
while (p != nullptr) {
Node* tmp = p;
p = p->next;
delete tmp;
}
delete m_pHead;
m_pHead = nullptr;
}
// 头插入
void insertHead(int data) {
Node* tmp = new Node(data);
tmp->next = m_pHead->next;
m_pHead->next = tmp;
// 更新尾部节点
if (m_pHead == m_pTailNode) {
m_pTailNode = tmp;
}
}
// 尾部插入
void insertTail(int data) {
Node* tmp = new Node(data);
m_pTailNode->next = tmp;
m_pTailNode = tmp;
}
// 查找
bool find(int data) {
// 遍历链表
Node* firstdata = m_pHead->next;
while (firstdata != nullptr) {
if (firstdata->data == data) {
return true;
}
firstdata = firstdata->next;
}
return false;
}
// 删除第一个元素
void deleteNode(int data) {
Node* firstdata = m_pHead->next;
Node* tmp = m_pHead;
while (firstdata != nullptr) {
if (firstdata->data == data) {
tmp->next = firstdata->next;
return;
}
tmp = firstdata; // 记录上一个节点
firstdata = firstdata->next;
}
}
// 删除所有的 value 节点
void deleteNodeAll(int data) {
Node* firstdata = m_pHead->next;
Node* tmp = m_pHead;
while (firstdata != nullptr) {
if (firstdata->data == data) {
tmp->next = firstdata->next;
} else {
tmp = firstdata; // 记录上一个节点
}
firstdata = firstdata->next;
}
}
// 遍历链表
void printNode() {
Node* p = m_pHead->next;
while (p) { // p 指向最后一个节点的后继节点，nullptr
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
private:
// int 节点和 Node 指针
struct Node {
Node(int da = 0) : data(da), next(nullptr) {}
int data;
Node* next;
};
Node* m_pHead;
Node* m_pTailNode;
// 添加一个节点避免每次尾插时都是遍历一遍
};
void test() {
LinkList list;
list.insertHead(1);
list.insertHead(2);
list.insertHead(3);
list.insertHead(3);
std::cout << list.find(4) << std::endl;
std::cout << list.find(3) << std::endl;
list.insertTail(4);
list.insertTail(5);
list.insertTail(6);
// 删除一个 元素
list.deleteNodeAll(3);
list.printNode();
}
运行结果：
0121456
优点：
缺点：
对应了 leetcode 206 https://leetcode.cn/problems/reverse-linked-list/description/
题目描述： 示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2： 输入：head = [1,2] 输出：[2,1]
示例 3： 输入：head = [] 输出：[]
**解题思路：**将逆序和头插联系起来。力扣上是个无头链表，需要 new 一个头部，并且置空，然后将原来的链表通过头插入链表内。
p->next = head->next; head->next=p; p = q;
ListNode* reverseList(ListNode* head) {
ListNode *newHead = new ListNode(-1, nullptr);
ListNode *currentNode = head;
while (currentNode != nullptr) {
// 记录下一个节点
ListNode *tmp = currentNode->next;
// 头插
currentNode->next = newHead->next;
newHead->next = currentNode;
currentNode = tmp;
}
std::unique_ptr<ListNode> ptr(newHead);
return newHead->next;
}
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 这个链表是一个无头链表。
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
**思路：**采用双指针方式，p 和 q 同时指向 Head, 假如求倒数第 3 个节点，p 向前移动 3 个节点，然后 p q 同时移动，当 p->next 等于空时候，q 指向的就是倒数第 k 个节点的前一个节点，然后直接 q->next = q->next->next 即可；
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 这道题，可以不使用 dummy，因为相对位置不变。
ListNode *pslow = head;
ListNode *pfast = head;
// p 先走 n + 1 步，指向删除的前一个
for (int i = 0; i < n; ++i) {
pfast = pfast->next;
}
// 两个一起走，知道 pfast 走到最后一个节点
while (pfast->next != nullptr) {
pfast = pfast->next;
pslow = pslow->next;
}
// 此时 slow 指向了删除的前一个节点
pslow->next = pslow->next->next;
return head;
}
题目描述： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2： 输入：l1 = [], l2 = [] 输出：[]
示例 3： 输入：l1 = [], l2 = [0] 输出：[0]
**解题思路：**使用双指针思想。对于无头链表，先判断哪个链表的头结点最小；然后按照顺序插入到最小的链表中。当一个链表插入完毕后，将其他直接插入进来即可。 先申请一个节点作为合并之后的节点的头部。使用两个指针 p 和 q 分别指向 link1 和 link2，遍历来比较这两个链表，将较小的元素插入到新的头部。最后，哪个不为空，newLinkCurrent->next = (p == nullptr ? q : p);
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// 指向待插入的位置
if (list1 == nullptr && list2 == nullptr) {
return nullptr;
}
if (list1 == nullptr) {
return list2;
}
if (list2 == nullptr) {
return list1;
}
ListNode *phead = nullptr;
if (list1->val < list2->val) {
phead = list1;
list1 = list1->next;
} else {
phead = list2;
list2 = list2->next;
}
phead->next = nullptr;
ListNode *ptail = phead;
while (list1 != nullptr && list2 != nullptr) {
if (list1->val < list2->val) {
ptail->next = list1;
ptail = list1;
list1 = list1->next;
} else {
ptail->next = list2;
ptail = list2;
list2 = list2->next;
}
}
// 看哪个链表提前为空
// if (list1 != nullptr)
// {
// ptail->next = list1;
// }
// else if (list2 != nullptr)
// {
// ptail->next = list2;
// }
// 使用三目运算符实现
ptail->next = (list1 != nullptr) ? list1 : list2;
return phead;
}
题目描述： 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
**解题思路：**使用两个指针，快指针和慢指针，分别从头节点出发，快指针每次走两个格子，慢指针每次走一个格子，如果两个指针在途中相遇，说明这个链表有环。
**原理说明：**为什么快指针一定遇上慢指针？相对于慢指针，快指针比慢指针只多一个节点，这就相当于慢指针不移动，快指针每次走一个节点，所以快指针一定会遇到慢指针。
**数学推导：**快慢指针相遇时走过的总节点计算。 假设从头结点到环形入口节点的节点数为 x；环形入口节点到 fast 指针与 slow 指针相遇节点时的节点数量为 y。从相遇节点再到环形入口节点数为 z。
fast 走过的路径为：fast 至少走过一圈，fast 一定是追赶慢指针。 x + y + z + y slow 走过的路径为：x + y 列出等式：因为快指针每次走两步，慢指针每次走一步，所以快指针走过的路程是慢指针的两倍。 (x + y + z + y) = 2 * (x + y) x + z = 2 * x x = z 最后得到 x = z ; 说明从相遇节点再次到环的入口距离与从头结点到环的入口距离相同。
ListNode *detectCycle(ListNode *head) {
// x = z
ListNode *slow = head;
ListNode *fast = head;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next; // 快指针每次走两个格子
slow = slow->next; // 慢指针每次走一个格子
if (slow == fast) // 相遇节点
{
// 相遇后，慢指针从头开始走，每次走一个格子
// 快指针从相遇位置走，每次走一个格子
slow = head;
while (fast != slow) {
fast = fast->next;
slow = slow->next;
}
return fast;
}
}
return nullptr;
}
**代码细节：**上面代码中：while (fast != nullptr && fast->next != nullptr) 这样判断目的？ fast 不为空，这样才能访问 fast->next fast->next 不为空，这样才能访问 fast->next->next
题目描述： 给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。 图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构。
**解题思路：**两个指针分别指向两个链表，分别走完后，记录下各个链表长度；len1 - len2 = diff; 长链表先走 diff 个元素，然后两个链表一起走，每次走一步都要判断是否等； 相等就是两个链表的交点
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
/* 解题思路：两个指针分别指向两个链表，分别走完后，记录下各个链表长度；len1 - len2 = diff; 长链表先走 diff 个元素，然后两个链表一起走，每次走一步都要判断是否等； 相等就是两个链表的交点 */
// 记录 len1 和 len2 长度
ListNode *pa = headA;
ListNode *pb = headB;
int len1 = 0;
int len2 = 0;
while (pa != nullptr) {
len1++;
pa = pa->next;
}
while (pb != nullptr) {
len2++;
pb = pb->next;
}
pa = headA;
pb = headB;
int diff;
if (len1 > len2) {
diff = len1 - len2;
// A 先走 dif 步
for (int i = 0; i < diff; ++i) {
pa = pa->next;
}
} else {
diff = len2 - len1;
// A 先走 dif 步
for (int i = 0; i < diff; ++i) {
pb = pb->next;
}
}
while (pa != nullptr && pb != nullptr) {
if (pa == pb) {
return pa;
}
pa = pa->next;
pb = pb->next;
}
return nullptr;
}
**时间复杂度分析：**O(m + n),其中 m + n 分别是 headA 和 headB 的长度。
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
示例 1：
输入：head = [1,2,3,4] 输出：[2,1,4,3]
示例 2： 输入：head = [] 输出：[]
示例 3： 输入：head = [1] 输出：[1]
提示： • 链表中节点的数目在范围 [0, 100] 内 • 0 <= Node.val <= 100
解题思路： 1 交换相邻的两个节点；
ListNode* swapPairs(ListNode* head) {
ListNode *dummyHead = new ListNode(-1);
dummyHead->next = head;
ListNode *current = dummyHead;
// 保证够两个节点
while (current->next != nullptr && current->next->next != nullptr) {
// 记录连续相邻的两个节点
ListNode *temp1 = current->next;
ListNode *temp2 = current->next->next->next;
current->next = current->next->next; // 步骤 1
current->next->next = temp1; // 步骤 2
current->next->next->next = temp2; // 步骤 3
// current 移动两位，准备下一轮交换
current = current->next->next; // 移动两位
}
std::unique_ptr<ListNode> ptr(dummyHead);
return dummyHead->next;
}
**反转链表：**使用头插入法。如果链表没有头节点，那就 new 一个头结点，使用一个指针指向头结点，另一个指针指向头的下一个节点；然后头部指针和下一个节点指针断开；当 p!=nullptr 时，依次采用头插入方式插入。核心插入如下： p->next = phead->next phead->next = p; p = p->next;
**删除倒数第 N 个节点：**使用双指针方法，头指针先移动 N 个节点，然后两个指针一起移动，判断条件时，p->next != nullptr 时，直接返回。最后 q 指向的待删除节点的前一个节点。
**链表相交：**使用双指针，各自遍历一遍链表，对比两个链表长度，长度长的链表先向前移动 diff = len1 – len2 个元素，然后一起移动；每次移动都判断是否相等，相等的就是交点。
**环形链表：**x + y + z + y = 2(x + y),最后得出 x = z,也就是快指针到相遇节点与慢指针从头到相遇节点的距离相同。