本文原本是对链表学习的记录笔记 因为约瑟夫问题笔记经典就拿来做大题材了，要是没学过链表或者链表还不熟悉的伙伴可以慢慢读，要是以及学过链表了，纯粹来看全新的解题思路的 可以用目录传送门往下跳
那么 开始吧
引言：为什么学习链表是数据结构与算法的必备知识
链表是数据结构与算法中最基本、最常用的数据结构之一。它在实际应用中具有重要性和优势，不仅在面试中扮演着重要角色，而且在竞赛中也占据相当比重。 根据广泛的面试经验和回馈，链表问题是面试中常见的考点之一，并且经常出现在技术公司的编程面试中。链表问题可以考察面试者对数据结构的理解、编码能力以及解决复杂问题的能力。掌握链表的基本操作和常见问题解法，可以帮助面试者在面试过程中更好地展现自己的能力。 其次，我们来分析链表在面试题中的比重。虽然具体比例会因面试的难度和类型而有所变化，但链表问题通常占据了相当大的比重。根据统计数据，链表问题在技术公司的编程面试中占据了约20%至30%的问题比例。这意味着，如果一个面试者没有对链表问题进行足够的准备，可能会错失相当多的机会。 此外，在竞赛中，链表问题同样具有一定的比重。在算法竞赛中，链表常常被用作构建和实现其他复杂数据结构的基础，如栈、队列和图等。因此，掌握链表的知识和技巧，对于在竞赛中迅速解决问题、提高算法效率至关重要。
而本文从基础概念出发，又引入到实战面试题当中，希望能从中带给读者一些帮助
话不多说 以下是正文 可以按照需要跳到自己需要的部分
单链表：定义、特点与基本操作
解释单链表的概念、结构和节点关系
单链表是一种由节点组成的数据结构，每个节点包含一个值和指向下一个节点的指针。这种结构使得单链表具有高效的插入和删除操作，但查找操作相对耗时。
单链表的抽象形态表现
在定义单链表的抽象形态时，我们可以通过表格框来展现其节点形态：
代码语言：javascript复制struct Node {
int data;
Node* next;
};这里的data表示节点的数据，next表示指向下一个节点的指针。
示例链表抽象形态表现
以下是一个示例链表的抽象形态表现，我们用表格框展示链表的结构：
代码语言：javascript复制 --------- --------- ---------
| data | | data | | data |
--------- --------- ---------
| next | -> | next | -> | nullptr|
--------- --------- ---------
Node 1 Node 2 Node 3单链表的基本操作
插入操作
在头部插入节点
代码语言：javascript复制void insertAtHead(Node*& head, int value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
}插入节点后的抽象形态表现：
代码语言：javascript复制 --------- --------- --------- ---------
| value | | data | | data | | data |
--------- --------- --------- ---------
| next | -> | next | -> | next | -> | nullptr|
--------- --------- --------- ---------
New Node Node 1 Node 2 Node 3在尾部插入节点
代码语言：javascript复制void insertAtTail(Node*& head, int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
}
}删除操作
删除头节点
代码语言：javascript复制void deleteAtHead(Node*& head) {
if (head == nullptr) {
return;
}
Node* temp = head;
head = head->next;
delete temp;
}删除尾节点
代码语言：javascript复制void deleteAtTail(Node*& head) {
if (head == nullptr) {
return;
}
if (head->next == nullptr) {
delete head;
head = nullptr;
return;
}
Node* temp = head;
while (temp->next->next != nullptr) {
temp = temp->next;
}
delete temp->next;
temp->next = nullptr;
}查找操作
遍历查找
代码语言：javascript复制Node* search(Node* head, int value) {
Node* temp = head;
while (temp != nullptr) {
if (temp->data == value) {
return temp;
}
temp = temp->next;
}
return nullptr;
}递归查找
代码语言：javascript复制Node* searchRecursive(Node* head, int value) {
if (head == nullptr) {
return nullptr;
}
if (head->data == value) {
return head;
}
return searchRecursive(head->next, value);
}单链表的案例分析
LCR 078. 合并 K 个升序链表
给定一个链表数组，每个链表都已经按升序排列。
请将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
代码语言：javascript复制输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6示例 2：
代码语言：javascript复制输入：lists = []
输出：[]示例 3：
代码语言：javascript复制输入：lists = [[]]
输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4
题目分析： 题目要求合并K个升序链表，其中每个链表可能包含0个或多个节点。我们需要以升序顺序返回合并后的链表。
解题思路： 为了解决这个问题，我们可以使用优先队列来维护所有的头节点，并依次弹出最小的头节点，并将其对应的链表的下一个节点插入到队列中。这个过程可以看作是归并排序的一部分，因为它类似于归并排序中合并两个有序数组的操作。这种方法的时间复杂度为O(Nlogk)，其中k是链表数，N是所有链表中的节点数。
代码解读：
- 定义一个优先队列，将所有的头节点添加到队列中。
- 定义一个哨兵节点，方便处理边界情况。
- 不断弹出最小的头节点，并将其对应的链表的下一个节点添加到队列中。
- 返回哨兵节点的下一个节点作为合并后的链表头。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
// 定义一个链表节点比较函数，用于优先队列的排序
int cmp(const void* a, const void* b) {
return (*((struct ListNode**)a))->val - (*((struct ListNode**)b))->val;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
// 创建一个优先队列
struct ListNode** pq = (struct ListNode**)malloc(sizeof(struct ListNode*) * listsSize);
int size = 0;
// 将所有的头节点添加到队列中
for (int i = 0; i < listsSize; i ) {
if (lists[i]) {
pq[size ] = lists[i];
}
}
// 使用自定义比较函数对队列中的元素进行排序
qsort(pq, size, sizeof(struct ListNode*), cmp);
// 定义一个哨兵节点，方便处理边界情况
struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
dummy->val = -1;
dummy->next = NULL;
struct ListNode* cur = dummy;
// 不断弹出最小的头节点，并将其对应的链表的下一个节点插入到队列中
while (size > 0) {
struct ListNode* node = pq[0];
cur->next = node;
cur = cur->next;
if (node->next) {
pq[0] = node->next;
} else {
pq[0] = pq[--size];
}
if (size > 0) {
// 对队列中的元素重新排序
int i = 0, j = 2 * i 1;
while (j < size) {
if (j 1 < size && pq[j 1]->val < pq[j]->val) {
j ;
}
if (pq[j]->val < pq[i]->val) {
struct ListNode* tmp = pq[i];
pq[i] = pq[j];
pq[j] = tmp;
i = j;
j = 2 * i 1;
} else {
break;
}
}
}
}
return dummy->next;
}. 双链表：定义、特点与基本操作
1.1 介绍双链表的定义和结构
在计算机科学中，双链表（Doubly Linked List）是一种常见的数据结构，它由一系列节点组成，每个节点包含两个指针，分别指向前一个节点和后一个节点，形成一个双向链表。与单链表相比，双链表可以更高效地进行向前和向后遍历，但也因为需要额外的指针而占用更多的内存空间。
下面是一个双链表节点的抽象形态表现：
节点结构 |
|---|
数据 |
前驱指针 |
后继指针 |
在这个表格框中，我们可以看到双链表节点的三个属性：数据、前驱指针和后继指针。数据存储了节点所需的信息，而前驱指针和后继指针则分别指向了前一个节点和后一个节点，使得节点之间能够互相连接。
1.2 学习双链表的基本操作：插入、删除、查找等
接下来，让我们一起学习双链表的基本操作，包括插入、删除和查找。
插入操作
在双链表中，插入操作可用于在任意位置插入一个新节点。下面是一个用 C 语言实现的双链表插入操作的示例代码：
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
void insert(struct Node** head, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
} else {
struct Node* current = *head;
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
new_node->prev = current;
}
}在上述代码中，我们定义了一个结构体 Node，表示双链表的节点。insert 函数用于向双链表中插入一个新节点。如果双链表为空，则将新节点作为头节点；否则，遍历双链表至末尾，将新节点插入到最后一个节点之后。
删除操作
删除操作允许我们从双链表中移除指定节点。下面是一个用 C 语言实现的双链表删除操作的示例代码：
代码语言：javascript复制void delete(struct Node** head, int data) {
struct Node* current = *head;
while (current != NULL) {
if (current->data == data) {
if (current->prev != NULL) {
current->prev->next = current->next;
}
if (current->next != NULL) {
current->next->prev = current->prev;
}
if (current == *head) {
*head = current->next;
}
free(current);
return;
}
current = current->next;
}
}在上述代码中，我们定义了一个 delete 函数，用于从双链表中删除包含指定数据的节点。通过遍历双链表，我们找到目标节点后，更新前驱和后继节点的指针，并正确处理头节点的情况。最后，释放目标节点的内存。
查找操作
查找操作用于确定双链表中是否存在包含特定数据的节点。下面是一个用 C 语言实现的双链表查找操作的示例代码：
代码语言：javascript复制int search(struct Node* head, int data) {
struct Node* current = head;
while (current != NULL) {
if (current->data == data) {
return 1;
}
current = current->next;
}
return 0;
}在上述代码中，我们定义了一个 search 函数，用于在双链表中搜索包含特定数据的节点。通过遍历双链表，我们可以确定是否存在满足条件的节点。
【链表应用】约瑟夫问题
上面铺垫了那么多 其实也只是为了解决问题而做的嘛 那么现在我们来面对一个实际的问题 约瑟夫问题 （典中典了属于是）
约瑟夫问题（Josephus Problem）是一个经典的数学问题，它的形式是：n个人围成一圈，从第k个人开始报数，数到m的那个人出列，然后从下一个人开始重新报数，直到最后剩下一个人。这个问题可以用链表来解决。 我们可以使用循环链表来模拟这个过程。具体地，我们先创建一个有n个节点的循环链表，每个节点代表一个人。然后，我们从第k个人开始，遍历链表并数m个人，将第m个人删除并输出，然后从下一个人开始重新报数，直到只剩下一个人为止。
下面是一个使用单向循环链表解决约瑟夫问题的示例代码：
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
void create_circle(struct Node** head, int n) {
struct Node* current = *head;
for (int i = 1; i <= n; i ) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = i;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
current = new_node;
} else {
current->next = new_node;
current = new_node;
}
}
current->next = *head;
}
void josephus(struct Node** head, int k, int m) {
struct Node* current = *head;
for (int i = 1; i < k; i ) {
current = current->next;
}
while (current->next != current) {
for (int i = 1; i < m; i ) {
current = current->next;
}
struct Node* temp = current->next;
printf("%d ", temp->data);
current->next = temp->next;
free(temp);
}
printf("%dn", current->data);
*head = NULL;
}
int main() {
struct Node* head = NULL;
int n, k, m;
scanf("%d %d %d", &n, &k, &m);
create_circle(&head, n);
josephus(&head, k, m);
return 0;
}在上述代码中，我们首先使用 create_circle 函数创建了一个有n个节点的循环链表，每个节点的数据为从1到n的整数。接着，我们使用 josephus 函数解决约瑟夫问题。该函数从第k个人开始遍历链表并数m个人，删除第m个人并输出，直到只剩下一个人为止。
运行程序时，输入n、k和m的值，即可得到最后留下的人的编号。
当然了！除了使用链表来解决约瑟夫问题，还有一种更巧妙的思路可以用数学方法直接求解。
假设n个人围成一圈，从第k个人开始报数，数到m的那个人出列。我们可以用一个递推公式来求解最后留下的人的编号。
首先，我们定义一个函数f(n, m)表示在n个人中，每次数m个人后剩下的人的编号。根据题意，我们知道当只有一个人时，即n=1时，这个人的编号为1，所以我们有基本情况：f(1, m) = 1。
接下来，我们考虑n个人的情况。当第一个人被数到并出列后，剩下的人变成了n-1个人，同时原来的第m 1个人变成了新的第一个人。因此，我们可以得到递推关系式：
f(n, m) = (f(n-1, m) m) % n
其中，%表示取模运算。通过这个递推关系式，我们可以从n=1开始递推，直到n等于给定的人数。
下面是使用递推公式解决约瑟夫问题的示例代码：
代码语言：javascript复制#include <stdio.h>
int josephus(int n, int k, int m) {
if (n == 1) {
return 1;
} else {
return (josephus(n-1, k, m) m) % n;
}
}
int main() {
int n, k, m;
printf("请输入人数n：");
scanf("%d", &n);
printf("请输入起始位置k：");
scanf("%d", &k);
printf("请输入报数m：");
scanf("%d", &m);
int last_person = josephus(n, k, m);
printf("最后留下的人的编号为：%dn", last_person);
return 0;
}运行程序时，输入n、k和m的值，即可得到最后留下的人的编号。
通过使用递推公式，我们可以直接求解约瑟夫问题，避免了构建链表和模拟报数的过程。这种方法更加简洁、高效，并且易于理解和实现。
面试官一看，眉毛邹了起来，递推可以是可以 但是这资源利用....嘶小伙子不懂得勤俭持家呀，万一栈溢出了怎么办？他正想微笑告诉你，小伙子回去等通知吧
你说 别急 因为我还有又简单又能节约资源的办法 --环形链表来解决这个问题
于是就有了下文
使用环形链表可以很方便地解决约瑟夫问题。我们可以按照如下步骤进行：
- 创建一个含有n个结点的环形链表，表示围成一圈的n个人。
- 从第k个人开始报数，每次数到m的那个人出列，直到只剩下一个人为止。
- 得到最后留下的人的编号。
下面是使用C语言编写的基于环形链表的解决约瑟夫问题的示例代码：
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} Node;
Node *createList(int n) {
Node *head = NULL, *prev = NULL;
for (int i = 1; i <= n; i ) {
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = i;
if (prev == NULL) {
head = new_node;
} else {
prev->next = new_node;
}
prev = new_node;
}
prev->next = head; // 链接首尾结点，形成环形链表
return head;
}
int josephus(Node *head, int k, int m) {
Node *prev = NULL, *curr = head;
for (int i = 1; i < k; i ) {
prev = curr;
curr = curr->next;
}
while (curr->next != curr) { // 只剩下一个人时退出循环
for (int i = 1; i < m; i ) {
prev = curr;
curr = curr->next;
}
prev->next = curr->next; // 删除当前结点
Node *temp = curr;
curr = curr->next;
free(temp);
}
return curr->data; // 返回最后留下的结点的编号
}
int main() {
int n, k, m;
printf("请输入人数n：");
scanf("%d", &n);
printf("请输入起始位置k：");
scanf("%d", &k);
printf("请输入报数m：");
scanf("%d", &m);
Node *head = createList(n);
int last_person = josephus(head, k, m);
printf("最后留下的人的编号为：%dn", last_person);
return 0;
}在上述代码中，我们定义了一个名为 createList 的函数，用于创建含有n个结点的环形链表；定义了一个名为 josephus 的函数，用于解决约瑟夫问题。在 main 函数中，我们首先输入人数n、起始位置k和报数m的值，然后调用 createList 函数创建环形链表，并调用 josephus 函数求解并输出最后留下的人的编号。
通过使用环形链表来解决约瑟夫问题，我们避免了构建数组和模拟报数的过程，使得代码更加简洁、高效，并且易于理解和实现。
面试官说 还不错小伙子 第一关算你过了
当然了 未完待续.....
下篇文章我将使用腾讯和阿里的面试题讲解链表知识点 敬请关注哈 有兴趣的小伙伴可以关注我的专栏 里面全是由浅入深的讲解算法的文章 保障让每个小白也能轻易学会http://t.csdnimg.cn/wlBwt
