链表核心概念与经典算法题解析
一、前言
接下来进入基础数据结构部分。
二、链表
2.1 本质
链表就是把数据离散开。
2.2 误区
头结点:不存任何数据
首元结点:存放着第一个数据
2.3 思路
- 根据题意选择合适的链表类型,如:单链表(带或不带头节点)
- 模拟遍历或快慢指针思想
2.4 题型
2.4.1 LeetCode
-
- 反转链表(头插法)两种思路:
- 头插法:
p = q; q = p->next; p->next = NULL;从第一个节点开始,挨个摘下每一个节点,摘下后用头插法建立新的链表
- 环形链表 II题意:判断有没有环以及从哪个节点开始进入环的(类似于跑步套圈的情况)。思路:如果有环,总有一天快指针会和慢指针相遇,并且快慢指针永远不会跑到空的地方;如果没环,快指针会很快指向空的地方。如何看从哪里开始进入环呢?快慢指针:快慢指针相遇一定是在圈里相遇。假设相遇点是
x,f指针走的快,先绕圈;s指针走的慢,后开始绕圈。f指针走了a + b,继续走;s指针先走了a,进入圈刚走了b就和f指针相遇了。此时,f已经跑了 n 圈,a + n * (b + c) + b。如图:
快指针和慢指针走,当它们两个相遇的时候,快指针就停下来,在用一个慢指针从起点开始走,慢指针继续走,当第一个慢指针又和第二个慢指针相遇的时候,就是开始进入圈的点。代码:
// 判断成环
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct ListNode {
int val;
ListNode *next;
} ListNode;
ListNode* detectCycle(ListNode* head) {
ListNode* f = head;
ListNode* s = head;
while (f != nullptr) {
s = s->next;
if (f->next == nullptr) {
return nullptr;
}
f = f->next->next;
if (s == f) {
ListNode* p = head;
while (p != s) {
p = p->next;
s = s->next;
}
return p;
}
}
return nullptr;
}
int main() {
int n, x;
// 建立单链表
cin >> n;
ListNode* head = nullptr;
ListNode* r = nullptr;
for (int i = 1; i <= n; i++) {
cin >> x;
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
s->val = x;
s->next = nullptr;
if (i == 1) {
head = s;
r = s;
} else {
// 尾插法
r->next = s;
r = s;
}
}
cin >> x;
ListNode* ans = detectCycle(head);
if (ans == nullptr) {
cout << "无环" << endl;
} else {
cout << ans->val << endl;
}
return 0;
}
LCR 140. 训练计划 II题意:给一个链表,找倒数第 cnt 个数据。思路:快慢指针。
ListNode *f = head;
ListNode *s = head;
while (f->next != nullptr) {
// f 先走,s 和 f 相距 cnt 个
if (cnt > 1) {
f = f->next;
cnt--;
continue;
}
// s 和 f 一起走
s = s->next;
f = f->next;
}
// 最后 s 指向的就是第 cnt 个
return s;
双指针:
t 指针:防止后面的部分丢失
p 指针:遍历链表
q 指针:为了使 p 指向前面的节点,q 指向前面的节点
代码:
// 反转链表——在原链表进行操作 (无 malloc)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct ListNode { // 定义链表节点
int val;
ListNode *next;
} ListNode;
ListNode* reverseList(ListNode* head) {
ListNode* p = head;
ListNode* q = nullptr;
while (p != nullptr) {
ListNode* t = p->next; // 防止后面的丢失
p->next = q; // 往前指
q = p; // 顺序不能反
p = t;
}
return q;
}
int main() {
int n, x;
cin >> n;
ListNode* head = nullptr;
ListNode* r = nullptr;
for (int i = 1; i <= n; i++) {
cin >> x;
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
s->val = x;
s->next = nullptr;
if (i == 1) {
head = s;
r = s;
} else {
// 尾插法
r->next = s;
r = s;
}
}
head = reverseList(head);
ListNode* s = head;
while (s != nullptr) {
cout << s->val << ;
s = s->next;
}
;
}
2.4.2 洛谷
- P1996 约瑟夫问题
2.5 补充
2.5.1 静态链表
用数组描述的链表(结构体数组)
2.5.2 跳表
在有序链表的基础上增加了'跳跃'的功能,对有序的链表实现二分查找功能。多层链表,每一层都有序,最下面的链表是最原始的链表(包括所有数据),从下往上节点折半提取元素上移。
三、小结
本篇结合经典题单、洛谷官方书籍等资料整理。


