循环链表
- 单链表局限性
- 单向循环链表
- 判断链表是否有环
- 思路
- code
- 找到链表入口
- 思路
- 代码结构与逻辑
- code
单链表局限性
单链表作为一种基本的数据结构，虽然在很多场景下都非常有用，但它也存在一些局限性：
-
单向访问：由于每个节点仅包含指向下一个节点的指针，因此只能从头节点开始按顺序向后遍历链表。这意味着如果要访问链表中距离头节点较远的节点，效率会比较低，时间复杂度为O(n)，其中n是链表的长度。
-
不支持随机访问：与数组不同，不能通过索引直接访问元素。要在单链表中查找一个特定的元素，通常需要从头节点开始逐个检查节点，直到找到目标节点或到达链表末尾。
-
额外的空间开销：单链表中的每个节点除了存储实际数据外，还需要额外的空间来存储指向下一个节点的指针。这相对于连续存储的数据结构（如数组）来说，可能会导致更高的内存占用率。
-
插入和删除操作的复杂性：尽管在已知位置的情况下，单链表的插入和删除操作可以在O(1)时间内完成，但要找到这个位置却可能需要遍历链表，从而需要O(n)的时间。此外，进行这些操作时还需要小心处理边界情况，比如插入到链表头部或删除最后一个节点等。
-
缓存性能差：与连续存储的数据结构相比，链表的节点在内存中可能分散存储，这会影响CPU缓存的命中率，进而影响程序的整体性能。
综上所述，虽然单链表具有动态大小调整的优点，但在访问速度、空间利用率以及缓存友好性等方面存在一定的局限性。根据应用场景的不同，选择合适的数据结构非常重要。
单向循环链表
- 循环链表(
Circular Linked List)是另一种形式的链式存储结构。其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。 - 当链表遍历时，判别当前指针
p是否指向表尾结点的终止条件不同。在单链表中，判别条件为p!=NULL或p->next!=NULL，而循环单链表的判别条件为p!=L或p->next!=L。
判断链表是否有环
思路
判断链表是否有环是一个经典的算法问题，通常有几种方法可以解决这个问题。最常用且效率较高的方法是“快慢指针”法（Floyd判圈算法），这种方法不仅能够判断链表中是否存在环，还能找到环的起点。以下是这种方法的基本思路：
快慢指针法
-
初始化两个指针：一个慢指针（slow）和一个快指针（fast）。慢指针每次只移动一步，而快指针每次移动两步。
-
同时移动两个指针遍历链表：
- 如果链表中存在环，那么快指针最终会追上慢指针（即两者相遇）。
- 如果链表中不存在环，快指针将会首先到达链表的末尾（null），此时可以确定链表没有环。
-
判断是否相遇：
- 如果快指针和慢指针相遇，则表明链表中有环。
- 如果快指针到达了链表的末尾（next为null），则说明链表没有环。
code
// 判断链表是否有环
int hasCycle(Node *head)
{
// 定义快慢指针，初始都指向头节点
Node *fast = head;
Node *slow = head;
// 当快指针和快指针的下一个节点不为空时，循环执行
while (fast != NULL && fast->next != NULL)
{
// 快指针每次移动两步，慢指针每次移动一步
fast = fast->next->next;
slow = slow->next;
// 如果快指针和慢指针相遇，说明链表有环，返回1
if (fast == slow)
return 1;
}
// 如果快指针和快指针的下一个节点为空，说明链表没有环，返回0
return 0;
}
int main(int argc, char const *argv[])
{
// 初始化链表
Node *list = InitList();
// 获取尾节点
Node *tail = GetTail(list);
tail = InsertTail(tail, 1);
tail = InsertTail(tail, 2);
tail = InsertTail(tail, 3);
Node *three = tail; // 保存第三个节点的地址
tail = InsertTail(tail, 4);
tail = InsertTail(tail, 5);
tail = InsertTail(tail, 6);
tail = InsertTail(tail, 7);
tail->next = three; // 将尾节点的next指向第三个节点，形成环
if (hasCycle(list))
printf("链表有环\n");
else
printf("链表没有环\n");
printf("打印链表：\n");
PrintList(list); // 遍历链表
return 0;
}
/* 判断链表是否有环 */
找到链表入口
思路
您的代码实现了一个检测链表中环的存在并找到环入口的算法。下面是对您提供的代码的详细分析和解释：
代码结构与逻辑
-
初始检查：
- 首先检查链表是否为空或者只有一个节点（
head == NULL || head->next == NULL），在这种情况下，直接返回NULL，因为这样的链表不可能有环。
- 首先检查链表是否为空或者只有一个节点（
-
快慢指针初始化：
- 定义两个指针：
fast和slow，均指向链表的头节点。这两个指针用于遍历链表，其中fast每次移动两步，而slow每次移动一步。
- 定义两个指针：
-
循环查找环：
- 在
while循环中，通过移动fast和slow来遍历链表。如果链表中存在环，那么fast和slow最终会在环内某个位置相遇。 - 如果
fast或fast->next为NULL，则表示链表没有环，函数返回NULL。
- 在
-
确认环的存在：
- 当
fast == slow时，表明链表中有环，跳出循环。
- 当
-
计算环的长度（非必要步骤）：
- 声明一个新的节点p，先指向fast，然后让p一直一定，当p再次指向相遇的节点时，说明环的长度已经计算完毕。
-
寻找环的入口：
- 接着，代码将
fast重新指向链表头部，并让fast先走之前计算得到的环长度步数。 - 然后，同时移动
fast和slow，每次各走一步，当它们相遇时的位置就是环的起始节点。
- 接着，代码将
code
- 思路：快慢指针，快指针每次走两步，慢指针每次走一步，如果快指针追上了慢指针，说明链表有环。
/**
* @description: 判断链表是否有环
* 思路：快慢指针，快指针每次走两步，慢指针每次走一步，如果快指针追上了慢指针，说明链表有环。
*/
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType; // 定义元素类型
typedef struct node // 定义节点类型
{
ElemType data;
struct node *next;
} Node;
/* 初始化一个单链表-造一个头节点 */
Node *InitList()
{
Node *head = (Node *)malloc(sizeof(Node)); // 为头节点分配内存
head->data = 0; // 头节点的数据域为0
head->next = NULL; // 头节点的指针域为空
return head; // 返回头节点
}
// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{
Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存
node->data = e; // 节点的数据域为e
node->next = NULL; // 节点的指针域为空
return node; // 返回节点
}
/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{
Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
p->data = e; // 在新节点的数据域存入数据e
p->next = L->next; // 新节点的指针域指向头节点的下一个节点(把L的NULL复制给新节点)
L->next = p; // 头节点的指针域指向新节点
return 1; // 返回1表示成功
}
/* 单链表 - 遍历 */
void TraverseList(Node *L)
{
Node *p = L->next; // 从头节点的下一个节点开始遍历
while (p != NULL) // 遍历到链表末尾
{
printf("%d ", p->data); // 输出节点的数据域,这里是%d,因为ElemType是int类型
p = p->next; // 移动到下一个节点
}
printf("\n"); // 换行
}
/* 单链表 - 尾插法 */
// 获取尾节点地址
Node *GetTail(Node *List)
{
Node *p = List; // 从头节点开始遍历
while (p->next != NULL) // 遍历到链表末尾
{
p = p->next; // 移动到下一个节点
}
return p; // 返回尾节点
}
/**
* @Description:单链表 - 尾插法插入数据
* @param {Node} *tail 尾节点
* @param {ElemType} e 插入的数据
* @return {*} 返回新的尾节点
*/
Node *InsertTail(Node *tail, ElemType e)
{
Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
p->data = e; // 在新节点的数据域存入数据e
tail->next = p; // 尾节点的指针域指向新节点
p->next = NULL; // 新节点的指针域为空
return p; // 返回新的尾节点
}
/**
* @Description:单链表 - 在链表尾部插入节点
* @param {Node} *tail 链表尾部节点
* @param {Node} *node 要插入的节点
* @return {Node *} 插入节点后的链表尾部节点
*/
Node *InsertTailWithNode(Node *tail, Node *node)
{
tail->next = node; // 尾节点的指针域指向要插入的节点
node->next = NULL; // 要插入的节点的指针域为空
return node; // 返回新的尾节点
}
/**
* @Description:单链表 - 在指定位置插入数据
* @param {Node} *L 单链表的头节点
* @param {int} pos 位置
* @param {ElemType} e 插入的数据
* @return {*}
*/
int InsertPosNode(Node *L, int pos, ElemType e)
{
// 用来保存插入位置的前驱节点
Node *p = L; // 从头节点开始遍历
int i = 0;
// 遍历链表-找到插入位置的前驱节点
while (i < pos - 1) // 遍历到插入位置的前驱节点
{
p = p->next; // 移动到下一个节点
i++;
if (p == NULL) // 判断是否到达链表末尾
{
printf("插入位置不合法\n");
return 0;
}
}
Node *newnode = (Node *)malloc(sizeof(Node)); // 创建一个新的节点
newnode->data = e; // 在新节点的数据域存入数据e
newnode->next = p->next; // 新节点的指针域指向插入位置的前驱节点的下一个节点
p->next = newnode; // 插入位置的前驱节点的指针域指向新节点
return 1;
}
/**
* @Description:单链表 - 删除指定位置的节点
* @param {Node} *L 单链表的头节点
* @param {int} pos 位置
* @return {*} 返回1表示成功
*/
int DeletePosNode(Node *L, int pos)
{
// 用来保存删除位置的前驱节点
Node *p = L; // 从头节点开始遍历
int i = 0;
// 遍历链表-找到删除节点的前驱节点
while (i < pos - 1) // 遍历到删除位置的前驱节点
{
p = p->next; // 移动到下一个节点
i++;
if (p == NULL) // 判断是否到达链表末尾
{
printf("删除位置不合法\n");
return 0;
}
}
if (p->next == NULL) // 判断删除位置是否合法
{
printf("删除位置不合法\n");
return 0;
}
Node *q = p->next; // 保存要删除的节点的地址
p->next = q->next; // 删除节点的前驱节点的指针域 指向 删除节点的下一个节点
free(q); // 释放删除节点的内存
return 1; // 返回1表示成功
}
int GetListLength(Node *L)
{
int length = 0;
Node *p = L; // 从头节点开始遍历,头节点算在内
while (p != NULL)
{
p = p->next;
length++;
}
return length;
}
void FreeList(Node *L)
{
Node *p = L->next; // 从头节点的下一个节点开始遍历,头节点不需要释放
Node *q = NULL; // 用来保存下一个节点的地址,q能掌握下一个节点的地址，这是灵魂所在
while (p != NULL)
{
q = p->next; // 保存下一个节点的地址
free(p); // 释放当前节点的内存
p = q; // 移动到下一个节点
}
L->next = NULL; // 头节点的指针域为空
}
// 查找倒数第k个节点
int findNodeFS(Node *L, int k)
{
Node *fast = L->next;
Node *slow = L->next;
for (int i = 0; i < k; i++)
{
fast = fast->next;
}
while (fast != NULL)
{
fast = fast->next;
slow = slow->next;
}
printf("倒数第%d个节点值为：%d\n", k, slow->data);
return 1;
}
// 查找两个节点共同后缀的起始位置
Node *findIntersectionNode(Node *headA, Node *headB)
{
if (headA == NULL || headB == NULL)
{
return NULL;
}
Node *p = headA;
int lenA = 0;
int lenB = 0;
// 遍历链表A，获取链表A的长度
while (p != NULL)
{
p = p->next;
lenA++;
}
// 遍历链表B，获取链表B的长度
p = headB;
while (p != NULL)
{
p = p->next;
lenB++;
}
Node *fast; // 快指针
Node *slow; // 慢指针
int step; // 两个单词之间数量的差值，可以用于快指针先走的步数
if (lenA > lenB)
{
step = lenA - lenB;
fast = headA;
slow = headB;
}
else
{
step = lenB - lenA;
fast = headB;
slow = headA;
}
// 让快指针先走step步
for (int i = 0; i < step; i++)
{
fast = fast->next;
}
// 快慢指针同步走，直到指向同一个节点退出循环
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
// 函数：RemoveEqualNodes
// 功能：删除链表中与给定值相等的节点
// 参数：Node *L：链表头指针，int n：链表的长度
// 返回值：无
void RemoveEqualNodes(Node *L, int n)
{
// TODO: 实现删除链表中与给定值相等的节点的功能
Node *p = L; // 定义一个指针p，指向链表的头节点
int index; // 定义一个变量index，作为数组下标使用
int *q = (int *)malloc(sizeof(int) * (n + 1)); // 在堆内存中分配一个数组，用来存储已经出现过的绝对值
/* 遍历数组，初始化为0 */
for (int i = 0; i < n + 1; i++)
{
*(q + i) = 0; // 初始化为0，表示没有出现过这个绝对值
}
while (p->next != NULL)
{
// 获取绝对值
index = abs(p->next->data); // 计算当前节点的绝对值，作为数组下标使用
if (*(q + index) == 0) // 如果这个绝对值没有出现过
{
*(q + index) = 1; // 标记为已经出现过
p = p->next; // 移动到下一个节点
}
else // 如果这个绝对值已经出现过,删除当前节点
{
Node *tempNode = p->next; // 保存要删除的节点的地址
p->next = tempNode->next; // 删除当前节点
free(tempNode); // 释放当前节点的内存
}
}
free(q); // 释放数组的内存
}
/**
* @description: 反转链表
* @param {Node} *head 头节点
* @return {*} 返回反转后的头节点
* note:
* 空指针检查:检查head是否为NULL，避免非法访问。
* 直接操作原头节点:反转完成后，将原头节点的next指向反转后的首节点（prev），无需新建头节点。
* 处理所有边界条件:链表为空（head->next为NULL）时，循环不会执行，直接返回head。
*
* 创建的三个节点是first,second,third 局部指针变量，不需要free释放内存
* first->next 或 first->data 是通过指针访问节点的成员。
* 直接写 first 表示操作指针本身（例如赋值或比较）。
*/
Node *ReverseList(Node *head)
{
if (head == NULL)
{
return NULL; // 处理空头节点情况
}
Node *first = NULL; // 定义一个指针first，指向空NULL，代表反转之后的尾
Node *second = head->next; // 定义一个指针second，指向头节点的下一个节点，代表当前节点
Node *third = NULL; // 定义一个指针third
while (second != NULL)
{
third = second->next; // 将third指向second的下一个节点，保存下一个节点的地址
second->next = first; // 将当前节点的next指针指向first，实现反转
first = second; // 将first指向second，移动到下一个节点，指针的赋值操作
second = third; // 将second指向third，移动到下一个节点
}
head->next = first; // 头节点的next指针指向first，实现反转
return head; // 返回新的头节点
}
int DeleteMidNode(Node *head)
{
Node *fastNode = head->next; // 快指针,先走一步，后面每次走两步
Node *slowNode = head; // 慢指针,每次走一步
/* 当快指针的下一个或者下一个的下一个是NULL，说明快指针已经走到了链表的末尾 */
while (fastNode != NULL && fastNode->next != NULL) // 快指针走到链表末尾时，慢指针指向的就是链表中间节点
{
fastNode = fastNode->next->next; // 快指针每次走两步
slowNode = slowNode->next; // 慢指针每次走一步
}
// 删除中间节点
Node *tempNode = slowNode->next; // 保存要删除的节点的地址
slowNode->next = tempNode->next; // 删除当前节点
free(tempNode); // free(tempNode) 释放的是 tempNode 所指向的内存，也就是被删除节点的堆内存
return 1; // 删除成功返回1
}
/**
* notes:问题：我自己创建了一个tempNode，然后free了tempNode，那么被删除的那个节点，没有被free，那么在内存里还存在被删除的节点吗？下面是deepseek的回答：
* tempNode 的作用：tempNode 是一个指针，它指向的是 slowNode->next，也就是链表中要被删除的节点。tempNode 本身只是一个指针变量，它存储的是被删除节点的内存地址。
* free(tempNode) 的作用：free(tempNode) 释放的是 tempNode 所指向的内存，也就是被删除节点的内存。free 并不会释放 tempNode 这个指针变量本身（指针变量是存储在栈上的），而是释放指针所指向的堆内存。
* 被删除节点的内存状态：当你调用 free(tempNode) 后，被删除节点的内存会被操作系统标记为“可回收”，这意味着这块内存不再属于你的程序，操作系统可以将其重新分配给其他部分使用。因此，被删除的节点在内存中不再有效。
*
* 总结：tempNode 会随着函数结束自动销毁；被删除的节点是通过 free 函数释放的内存。
*/
// 重新排列链表
void reOrderList(Node *head)
{
// TODO: 实现重新排列链表的功能
Node *fast = head; // 快指针,不需要从head->next开始，因为要找到中间节点（偶数个节点时，中间节点是中间两个节点的前一个节点,奇数个节点时，中间节点是中间那个节点）
Node *slow = head;
while (fast != NULL && fast->next != NULL) // 快指针走到链表末尾时，慢指针指向的就是链表中间节点
{
fast = fast->next->next;
slow = slow->next;
}
Node *first = NULL; // 用来保存反转后的链表的头节点
Node *second = slow->next; // 从中间节点开始反转
Node *third = NULL; // 用来保存下一个节点的地址
slow->next = NULL; // 中间节点的next指向NULL，从中间断开链表，分成两个链表，再合并两个链表
while (second != NULL)
{
third = second->next; // 保存下一个节点的地址
second->next = first; // 反转
first = second; // 移动到下一个节点
second = third; // 移动到下一个节点
}
// 合并两个链表
Node *p1 = head->next; // 从头节点的下一个节点开始遍历
Node *q1 = first; // 从反转后的链表的头节点开始遍历
Node *p2, *q2;
while ((p1 != NULL) && (q1 != NULL)) // 当两个链表都没有遍历完时，交替合并两个链表
{
p2 = p1->next; // 保存p1的下一个节点的地址
q2 = q1->next; // 保存q1的下一个节点的地址
p1->next = q1; // 交替合并两个链表，p1和q1交替连接，p2和q2交替连接，直到有一个链表遍历完为止
q1->next = p2; // 交替合并两个链表，p1和q1交替连接，p2和q2交替连接，直到有一个链表遍历完为止
p1 = p2; // 移动到下一个节点
q1 = q2; // 移动到下一个节点
}
}
// 判断链表是否有环
int hasCycle(Node *head)
{
// 定义快慢指针，初始都指向头节点
int fast_count = 0;
int slow_count = 0;
Node *fast = head;
Node *slow = head;
// 当快指针和快指针的下一个节点不为空时，循环执行
while (fast != NULL && fast->next != NULL)
{
// 快指针每次移动两步，慢指针每次移动一步
fast = fast->next->next;
slow = slow->next;
fast_count += 2;
slow_count++;
// 如果快指针和慢指针相遇，说明链表有环，返回1
if (fast == slow)
{
// printf("环的个数为：%d\n", (fast_count - slow_count)); // 计算环的个数
return 1;
}
}
// 如果快指针和快指针的下一个节点为空，说明链表没有环，返回0
return 0;
}
// 找到链表环的入口
Node *FindCycleListEntry(Node *head)
{
if (head == NULL || head->next == NULL)
return NULL; // 链表为空或只有一个节点，肯定无环
// 定义快慢指针，初始都指向头节点
Node *fast = head;
Node *slow = head;
// 当快指针和快指针的下一个节点不为空时，循环执行
while (fast != NULL && fast->next != NULL)
{
// 快指针每次移动两步，慢指针每次移动一步
fast = fast->next->next;
slow = slow->next;
// 如果快指针和慢指针相遇，说明链表有环，返回1
if (fast == slow)
{
break; // 跳出循环
}
}
// 如果没有环，返回NULL
if (fast == NULL || fast->next == NULL)
return NULL; // 链表为空或只有一个节点，肯定无环
// 计算环的长度
int LoopLength = 0; // 环的长度
Node *p = fast; // 保存相遇的节点
// 当p再次指向相遇的节点时，说明环的长度已经计算完毕
do
{
LoopLength++;
p = p->next; // 移动到下一个节点
} while (p != fast);
// 让快指针重新指向头节点，慢指针指向头节点
fast = head;
slow = head;
// 让快指针先走环的长度步数
for (int i = 0; i < LoopLength; i++)
{
fast = fast->next;
}
// 快慢指针同步走，直到指向同一个节点退出循环
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast; // 返回环的入口节点
}
int main()
{
// 初始化链表
Node *list = InitList();
// 获取尾节点
Node *tail = GetTail(list);
tail = InsertTail(tail, 1);
tail = InsertTail(tail, 2);
tail = InsertTail(tail, 3);
Node *CycleEntry = tail; // 保存环的入口节点
tail = InsertTail(tail, 4);
tail = InsertTail(tail, 5);
tail = InsertTail(tail, 6);
tail = InsertTail(tail, 7);
tail = InsertTail(tail, 8);
tail->next = CycleEntry; // 将尾节点的next指向环的入口节点，形成环
Node *p = FindCycleListEntry(list);
printf("环的入口节点为：%d\n", p->data); // 输出环的入口节点的值
return 0;
}
/* 找到链表环的入口 */
![P2036 [COCI 2008/2009 #2] PERKET（dfs）](https://i-blog.csdnimg.cn/direct/65c7e19c5904425d8666e1db514ab34e.png)
