【数据结构】循环链表

单链表局限性

单链表作为一种基本的数据结构，虽然在很多场景下都非常有用，但它也存在一些局限性：

1. 单向访问：由于每个节点仅包含指向下一个节点的指针，因此只能从头节点开始按顺序向后遍历链表。这意味着如果要访问链表中距离头节点较远的节点，效率会比较低，时间复杂度为O(n)，其中n是链表的长度。

2. 不支持随机访问：与数组不同，不能通过索引直接访问元素。要在单链表中查找一个特定的元素，通常需要从头节点开始逐个检查节点，直到找到目标节点或到达链表末尾。

3. 额外的空间开销：单链表中的每个节点除了存储实际数据外，还需要额外的空间来存储指向下一个节点的指针。这相对于连续存储的数据结构（如数组）来说，可能会导致更高的内存占用率。

4. 插入和删除操作的复杂性：尽管在已知位置的情况下，单链表的插入和删除操作可以在O(1)时间内完成，但要找到这个位置却可能需要遍历链表，从而需要O(n)的时间。此外，进行这些操作时还需要小心处理边界情况，比如插入到链表头部或删除最后一个节点等。

5. 缓存性能差：与连续存储的数据结构相比，链表的节点在内存中可能分散存储，这会影响CPU缓存的命中率，进而影响程序的整体性能。

综上所述，虽然单链表具有动态大小调整的优点，但在访问速度、空间利用率以及缓存友好性等方面存在一定的局限性。根据应用场景的不同，选择合适的数据结构非常重要。

单向循环链表

• 循环链表(Circular Linked List)是另一种形式的链式存储结构。其特点是表中最后一个节点的指针域指向头节点，整个链表形成一个环。
• 当链表遍历时，判别当前指针p是否指向表尾结点的终止条件不同。在单链表中，判别条件为 p!=NULL或 p->next!=NULL，而循环单链表的判别条件为p!=L 或 p->next!=L。

判断链表是否有环

思路

判断链表是否有环是一个经典的算法问题，通常有几种方法可以解决这个问题。最常用且效率较高的方法是“快慢指针”法（Floyd判圈算法），这种方法不仅能够判断链表中是否存在环，还能找到环的起点。以下是这种方法的基本思路：

快慢指针法

1. 初始化两个指针：一个慢指针（slow）和一个快指针（fast）。慢指针每次只移动一步，而快指针每次移动两步。

2. 同时移动两个指针遍历链表：

   • 如果链表中存在环，那么快指针最终会追上慢指针（即两者相遇）。
   • 如果链表中不存在环，快指针将会首先到达链表的末尾（null），此时可以确定链表没有环。

3. 判断是否相遇：

   • 如果快指针和慢指针相遇，则表明链表中有环。
   • 如果快指针到达了链表的末尾（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;// 如果快指针和慢指针相遇，说明链表有环，返回1if (fast == slow)return 1;}// 如果快指针和快指针的下一个节点为空，说明链表没有环，返回0return 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");elseprintf("链表没有环\n");printf("打印链表：\n");PrintList(list); // 遍历链表return 0;
}/* 判断链表是否有环 */

找到链表入口

思路

您的代码实现了一个检测链表中环的存在并找到环入口的算法。下面是对您提供的代码的详细分析和解释：

代码结构与逻辑

1. 初始检查：

   • 首先检查链表是否为空或者只有一个节点（head == NULL || head->next == NULL），在这种情况下，直接返回NULL，因为这样的链表不可能有环。

2. 快慢指针初始化：

   • 定义两个指针：fast 和 slow，均指向链表的头节点。这两个指针用于遍历链表，其中fast每次移动两步，而slow每次移动一步。

3. 循环查找环：

   • 在while循环中，通过移动fast和slow来遍历链表。如果链表中存在环，那么fast和slow最终会在环内某个位置相遇。
   • 如果fast或fast->next为NULL，则表示链表没有环，函数返回NULL。

4. 确认环的存在：

   • 当fast == slow时，表明链表中有环，跳出循环。

5. 计算环的长度（非必要步骤）：

   • 声明一个新的节点p，先指向fast，然后让p一直一定，当p再次指向相遇的节点时，说明环的长度已经计算完毕。

6. 寻找环的入口：

   • 接着，代码将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;                            // 头节点的数据域为0head->next = NULL;                         // 头节点的指针域为空return head;                               // 返回头节点
}// 初始化节点（带节点数据域参数）
Node *InitListWithElem(ElemType e)
{Node *node = (Node *)malloc(sizeof(node)); // 为节点分配内存node->data = e;                            // 节点的数据域为enode->next = NULL;                         // 节点的指针域为空return node;                               // 返回节点
}/*单链表 - 头插法*/
int InsertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); // 创建一个新的节点p->data = e;                            // 在新节点的数据域存入数据ep->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;                            // 在新节点的数据域存入数据etail->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;                            // 在新节点的数据域存入数据enewnode->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;        // 定义一个指针thirdwhile (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++;// 如果快指针和慢指针相遇，说明链表有环，返回1if (fast == slow){// printf("环的个数为：%d\n", (fast_count - slow_count)); // 计算环的个数return 1;}}// 如果快指针和快指针的下一个节点为空，说明链表没有环，返回0return 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;// 如果快指针和慢指针相遇，说明链表有环，返回1if (fast == slow){break; // 跳出循环}}// 如果没有环，返回NULLif (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;
}/* 找到链表环的入口 */