【笔记】数据结构|链表算法总结|快慢指针场景和解决方案|链表归并算法和插入算法|2012 42
受堆积现象直接影响的是：平均查找长度
产生堆积现象，即产生了冲突，它对存储效率、散列函数和装填因子均不会有影响，而平均查找长度会因为堆积现象而增大。
2012 42
参考灰灰考研
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀，则可共享相同的后缀存储空间，例如，“loaging”和“being”, 如下图所示。
设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为
请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)。
要求:
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时空复杂度。
（1）算法的基本思想
【解释为什么使用快慢指针】
假设一个链表比另一个链表长k个结点【比另一个节点长多少需要算出来，所以每个链表都需要先遍历一次，求出长度】，若需要两个链表同时到达尾节点，我们先在长链表上遍历k个结点，之后同步遍历两个链表。这样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所以它们肯定同时到达第一个公共结点。于是得到算法思路
①求它们的长度len1, len2；
②遍历两个链表，使p，q指向的链表等长；
④同步遍历两个链表，直至找到相同结点或链表结束。
typedef struct Node
{
int data;
struct node *next;
}node,*LinkList;
int Linklength(LinkList L)//求单链表长度
{
int k=0;
while(L!=NULL)
{
k++;
L=L->next;
}
return k;
}
void ShowList(LinkList L)//输出链表内容
{
while(L)
{
printf("%d->",L->data);
L=L->next;
}
printf("NULL");
printf("\n");
}
LinkList CreateList_end(int n)//尾插法建立链表
{
LinkList head=(LinkList)malloc(sizeof(node));
node *p,*e;
p = head;
int x;
for(int i=0; i<n; i++)//尾插法建立链表
{
e=(LinkList)malloc(sizeof(node));
scanf("%d",&x);
e->data=x;
p->next=e;
p=e;
}
p->next=NULL;//将链表的最后一个节点的指针域置空
head=head->next;//因为头结点为空，所以所以指向下一个节点这样才有数据域
return head;
}
## 实现方法一
LinkList *Find_1st_Common(LinkList str1,LinkList str2){
int len1=Linklength(str1),len2=Linklength(str2);
LinkList p,q;
for(p=str1;len1>len2;len1--)//使p指向的链表与q指向的链表等长
p=p->next;
for(q=str2;len1</len2;len2--)</n; i++)
q=q->next;
while(p->next!=NULL&&p->data!=q->data){ //查找共同后缀起始点
p=p->next; //两个指针同步向后移动
q=q->next;
}
return p; //返回共同后缀的起始点
}
## 实现方法二
//三目运算符
LinkList *Find_1st_Common(LinkList str1,LinkList str2){
LinkList p = str1;
LinkList q = str2;
int len1=Linklength(str1),len2=Linklength(str2);
for(p=str1;len1>len2;len1--)//使p指向的链表与q指向的链表等长
p=p->next;
for(q=str2;len1<len2;len2--)//使q指向的链表与p指向的链表等长
q=q->next;
while(p->data != q->data){
p = p?p->next:str1;
q = q?q->next:str2;
}
return p;
}
int main()
{
LinkList L1;
int n1;
printf("请输入L1链表的长度，以回车结束，然后输入结点的值：");
scanf("%d",&n1);
L1 = CreateList_end(n1);
printf("L1链表为：");
ShowList(L1);
LinkList L2;
int n2;
printf("请输入L2链表的长度，以回车结束，然后输入结点的值：");
scanf("%d",&n2);
L2 = CreateList_end(n2);
printf("L2链表为：");
ShowList(L2);
printf("\n");
printf("L1和L2公共后缀的起始节点（即相交结点）为：");
LinkList L3;
L3 = Find_1st_Common(L1,L2);
printf("%d",L3->data);
return 0;
}
链表
链表节点定义
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 辅助函数：创建链表（从前向后插入）
ListNode* createLinkedList(const std::vector<int>& elements) {
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
for (int element : elements) {
current->next = new ListNode(element);
current = current->next;
}
return dummy->next;
}
// 辅助函数：打印链表
void printLinkedList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
// 辅助函数：释放链表内存（避免内存泄漏）
void deleteLinkedList(ListNode* head) {
ListNode* temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
}
使用快慢指针的场景和解决方案
使用快慢指针（也称为“龟兔赛跑”算法）是一种解决特定类型问题的有效方法，特别是那些涉及到链表或数组遍历，并需要查找某种特定模式（如循环、中间节点等）的问题。快慢指针通过让两个指针以不同的速度遍历数据结构，从而有效地揭示出数据结构的某些隐藏特性。以下是一些使用快慢指针的常见原因及例子：
1. 检测链表中的环
原因：在单向链表中，有时可能会因为某些操作（如错误的节点连接）而形成环。使用快慢指针可以高效地检测这种环的存在。
例子：快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，那么快慢指针最终会在环内的某个节点相遇；如果链表无环，快指针将到达链表末尾的null。
2. 寻找链表的中间节点
原因：在单向链表中，直接找到中间节点通常需要遍历两次链表（第一次计算长度，第二次定位中间）。使用快慢指针可以在一次遍历中找到中间节点。
例子：快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾时，慢指针正好在链表的中间位置。注意，这里假设链表长度是奇数；如果是偶数，则“中间”通常定义为两个中间节点中的第一个。
3. 在有序链表中寻找特定值（如二分查找的变种）
原因：虽然这不是快慢指针最典型的用法，但在某些情况下，快慢指针可以用来加速在有序链表中的搜索过程，尤其是当你知道目标值大致位置时。
例子：快指针以较大的步长前进，慢指针以较小的步长前进，或者根据快指针的位置动态调整慢指针的步长，以逼近目标值。这不是传统意义上的快慢指针，但体现了快慢指针思想在搜索问题中的应用。
- 初始化：设置两个指针，一个称为“快指针”（或“大步指针”），另一个称为“慢指针”（或“小步指针”）。快指针的步长可以比慢指针大，但具体步长取决于你希望如何加速搜索。
- 移动指针：同时移动两个指针，但快指针每次移动的距离比慢指针远。例如，慢指针每次移动一个节点，而快指针每次移动两个或更多个节点。
- 比较与调整：
- 如果快指针越过了目标值（即快指针的当前值大于目标值，且快指针的前一个值小于等于目标值，但由于链表不支持向后访问，这通常是一个假设性的判断），则可以根据快指针的位置来调整搜索范围。例如，你可以将搜索范围缩小到快指针前一个节点与链表起始节点之间（如果快指针不是从起始节点开始的话）。
- 如果快指针还没有到达链表末尾且其当前值小于目标值，则继续移动两个指针。
- 如果快指针到达了链表末尾且没有找到目标值，那么目标值可能位于快指针最后遍历的节点之后（如果链表是有序的话）。
重复与收敛：重复上述步骤，直到快指针和慢指针相遇（这通常不会发生，因为我们不是真正地在寻找相遇点），或者直到搜索范围被缩小到足够小，以至于可以通过顺序遍历来找到目标值。
4. 求解约瑟夫环问题
原因：约瑟夫环是一个著名的理论问题，其中N个人围成一圈，按某种顺序报数，每报到M的人将被淘汰，然后从被淘汰的下一个人开始继续报数，直到所有人都被淘汰。使用快慢指针可以在链表上模拟这个过程。
例子：将N个人视为链表中的N个节点，快指针每次移动M步，慢指针每次移动1步。当快指针淘汰一个节点（即将其从链表中移除）后，快指针可能需要调整其位置以继续模拟报数过程。
5. 寻找环的入口：在检测到环后，将一个指针从头节点开始，另一个指针从相遇点开始，两个指针每次各移动一步，它们再次相遇的点即为环的入口。
合并链表
合并两个有序链表：使用两个指针分别遍历两个链表，比较指针所指向的节点值，将较小的节点接到新链表的末尾，并移动对应的指针，直到两个链表都被遍历完。
复制链表
复制复杂链表：对于包含random指针的链表，复制过程需要分三步进行：首先复制原始链表的每个节点并链接到原节点之后；然后设置复制节点的random指针；最后将链表拆分为原始链表和复制链表。
查找链表中的特定节点
查找倒数第k个节点：使用双指针，一个指针先走k步，然后两个指针同时走，当先走的指针到达链表末尾时，后走的指针所在位置即为倒数第k个节点。
链表的其他操作
旋转链表：将链表向右或向左旋转k个位置，可以通过先遍历链表得到长度，然后将链表首尾相接形成环，再根据旋转规则找到新的头节点。
链表排序
可以使用归并排序等算法对链表进行排序，排序过程中需要找到链表的中间节点以进行分治。
1. 插入排序（Insertion Sort）
基本思想：将链表分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的适当位置，直到所有元素都排序完成。
特点：
插入排序在链表排序中非常高效，因为链表支持快速的插入操作。
时间复杂度为O(n^2)，空间复杂度为O(1)（原地排序，不需要额外空间）。
2. 冒泡排序（Bubble Sort）
基本思想：通过重复地遍历链表，比较相邻元素的大小，并在必要时交换它们的位置，直到没有需要交换的元素为止。
特点：
冒泡排序虽然简单，但在链表上效率不高，因为链表的随机访问性能较差。
时间复杂度为O(n^2)，空间复杂度为O(1)。
3. 归并排序（Merge Sort）
基本思想：采用分治法，将链表分成两半，对每半部分递归地进行归并排序，然后将排序好的两半合并成一个有序链表。
特点：
归并排序在链表排序中非常高效，因为它利用了链表分割和合并的便利性。
时间复杂度为O(n log n)，空间复杂度为O(n)（需要额外的空间来存储递归过程中产生的临时链表）。
4. 快速排序（Quick Sort）
基本思想：选择一个元素作为基准（pivot），通过一趟排序将待排序的链表分割成独立的两部分，其中一部分的所有元素都比另一部分的所有元素要小，然后再按此方法对这两部分链表分别进行快速排序，整个排序过程可以递归进行，以达到整个链表变成有序链表。
特点：
快速排序在链表上的实现相对复杂，因为需要找到基准元素的前一个和后一个节点以便进行分割。
时间复杂度平均为O(n log n)，最坏情况下为O(n^2)，但这种情况很少见。
空间复杂度主要取决于递归的深度，平均为O(log n)，最坏情况下为O(n)（当链表已经有序或几乎有序时）。
对于链表排序来说，插入排序和归并排序是较为常用的算法，它们能够充分利用链表的特性来实现高效的排序。而冒泡排序虽然简单，但效率较低；快速排序在链表上的实现相对复杂；堆排序则通常不用于链表排序。
链表插入排序
ListNode* insertionSortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* dummy = new ListNode(0);
ListNode* sortedTail = dummy;
ListNode* current = head;
while (current != nullptr) {
if (sortedTail->next == nullptr || sortedTail->next->val >= current->val) {
// 直接插入到末尾
sortedTail->next = current;
sortedTail = sortedTail->next;
current = current->next;
sortedTail->next = nullptr; // 断开与原始链表的连接
} else {
// 向前寻找插入位置
ListNode* prev = dummy;
while (prev->next->val < current->val) {
prev = prev->next;
}
// 保存当前节点的下一个节点
ListNode* nextTemp = current->next;
// 将当前节点插入到找到的位置
current->next = prev->next;
prev->next = current;
// 移动到原始链表的下一个节点
current = nextTemp;
}
}
return dummy->next;
}
链表的归并排序
归并排序的实现需要递归地将链表分割成两半，对每半部分进行归并排序，然后将它们【合并】。这里一定用到了有序链表的合并。
我们需要一个函数来找到链表的中点，这通常通过快慢指针技术实现。然后，我们需要分割链表，这可以通过修改指针来实现，而不需要实际复制节点。最后，我们需要一个合并函数来合并两个已排序的链表。
需要4个函数
1. findMiddle
找到链表中点找到链表的中点（更准确地说是中点的前一个节点）。如果链表有奇数个节点，它返回中点前一个节点的指针；如果链表有偶数个节点，它可以选择返回中点前一个或中点本身（但在这个实现中，它总是返回中点前一个节点）。
2. splitList(ListNode head)：分割左右链表，并返回右链表的开头*
作用：根据 findMiddle 函数找到的中点位置，将链表分割成两个子链表。它修改了中点前一个节点的 next 指针，使其指向 nullptr，从而断开链表。
返回值：返回第二个子链表的头节点（即原链表后半部分的头节点）。
重要性：分割是归并排序递归过程中的关键步骤，因为它允许我们独立地对链表的两个子部分进行排序。
3. mergeTwoLists(ListNode l1, ListNode l2)：【合并有序链表】
作用：合并两个已排序**的链表 l1 和 l2 为一个新的已排序链表。它比较两个链表的头节点，选择较小的节点并将其添加到结果链表的末尾，然后递归地合并剩余的链表。
返回值：返回合并后链表的头节点。
重要性：合并是归并排序算法的最后一步，它将两个已排序的子链表组合成一个完整的已排序链表。
4. mergeSortList(ListNode* head)：【使用递归算法实现】
作用：对链表进行归并排序。如果链表为空或只有一个节点，它直接返回链表本身。否则，它使用 splitList 函数将链表分割成两个子链表，递归地对它们进行排序，然后使用 mergeTwoLists 函数将排序后的子链表合并成一个完整的已排序链表。
返回值：返回排序后链表的头节点。
重要性：这是归并排序链表的主函数，它协调了分割和合并的步骤，以实现对整个链表的排序。
// 辅助函数：找到链表的中点前一个节点
ListNode* findMiddle(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode* slow = head;
ListNode* fast = head;
ListNode* prevPtr = nullptr;
while (fast != nullptr && fast->next != nullptr) {
prevPtr = slow; //中间节点的前一个节点。使用slow赋值
slow = slow->next;
fast = fast->next->next;
}
// 如果链表长度是奇数，prevPtr 将指向中点的前一个节点
// 如果链表长度是偶数，我们可以选择 prevPtr 或 prevPtr->next 作为中点（这里选择 prevPtr->next）
// 但为了统一处理，我们总是让 prevPtr 指向中点的前一个节点（或 nullptr，如果链表只有一个节点）
return prevPtr;
}
// 辅助函数：分割链表
ListNode* splitList(ListNode* head) { //这里体现了寻找中点前一个结点的重要性，因为需要将中点前一个结点的next指针置空
if (head == nullptr) return nullptr;
ListNode* middlePrev = findMiddle(head);
if (middlePrev == nullptr) return nullptr; // 链表为空或只有一个元素
ListNode* middle = middlePrev->next;
middlePrev->next = nullptr; // 分割链表，使得链表可以分割成独立的左半部分和右半部分
return middle;
}
// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0); //辅助头节点
ListNode* tail = dummy;
while (l1 != nullptr && l2 != nullptr) { //遍历到后面有个链表空或者同时为空
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = (l1 != nullptr) ? l1 : l2; //合并非空链表剩余部分
ListNode* sortedList = dummy->next;
delete dummy; // 释放辅助节点
return sortedList;
}
// 归并排序链表
ListNode* mergeSortList(ListNode* head) { //递归实现
if (head == nullptr || head->next == nullptr) return head;
ListNode* middle = splitList(head); //中间节点
ListNode* left = mergeSortList(head);
ListNode* right = mergeSortList(middle);
return mergeTwoLists(left, right);
}
// 辅助函数：打印链表
void printLinkedList(ListNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->next;
}
std::cout << std::endl;
}
// 主函数，用于测试
int main() {
// 创建一个测试链表 4->2->1->3
ListNode* head = new ListNode(4);
head->next = new ListNode(2);
head->next->next = new ListNode(1);
head->next->next->next = new ListNode(3);
std::cout << "Original list: ";
printLinkedList(head);
// 对链表进行归并排序
head = mergeSortList(head);
std::cout << "Sorted list: ";
printLinkedList(head);
// 释放链表内存（避免内存泄漏）
// 注意：这里省略了实际的内存释放代码，因为它取决于链表的构建方式
// 你需要遍历链表并逐个删除节点
return 0;
}