当前位置：首页 > news >正文

力扣环形链表（1）进阶环形链表（2）及环形链表的约瑟夫问题

news 2025/6/27 2:53:24

为了加深对环形链表的理解和掌握，这两道题是很不错的选择。
这里所说环形链表不是一个圈圈的结构，而是带环链表。

链接：环形链表（1）

注意这里链表的长度

所以要注意链表是否为空
第一种方法，应该是比较容易想到的方法（偷鸡取脚）
遍历链表，将每个节点的val更改为一个不容易想到的值，如666666，当遇到一个666666时就返回true，如果在遍历过程中一直走到空都再没有遇到一个666666，那就返回false。
代码如下
bool hasCycle(struct ListNode *head) {struct ListNode*p=head;while(p){if(p->val!=666666){p->val=666666;p=p->next;}else return true;}return false;
}
这种方法明显是投机取巧，所以还有可能被抓到。
运行后还是也可以通过

双指针法（正经方法）
就想操场的跑道上，有跑的快的人和跑得慢的人，快的人会不断追上慢的人。
设置双指针，从head开始走，快指针一次跑两步，慢指针一次跑一步，链表中是有环的，快指针一定会抓到慢指针。
在慢指针进环时，快指针已经在环状里转圈圈了，慢指针一次走一步，快指针一次走两步，慢指针走半圈，快指针就走一圈。

代码如下
bool hasCycle(struct ListNode *head) {struct ListNode*slow=head,*fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){return true;}}return false;
}
一直找找找，如果有环一定会相遇。
思考：

如果快指针一次走3步，还可以保证能抓到慢指针吗？

假使慢指针进环时，快慢指针差距m个位置，每次快指针与慢指针的距离差距减小为2，有两种情况。

m为偶数

每次距离都减小2
m-2
m-4
m-6
…
4
2
0
最终快指针会遇到慢指针。
2. m为奇数
m-2
m-4
…
3
1
-1
当相差为-1时，快慢指针间的距离变为了m-1。
假设C是环的长度，这里的-1即为C-1；如果环的长度为偶数，那么快慢指针最近的距离为1，因为一次减小的距离为2，所以永远也追不上慢指针。

环形链表（2）

和第一道题不一样的是这道题如果有环，就返回入环的第一个节点，如果链表无环，就返回NULL。
接下来就要进行分析
当快指针与慢指针相遇时，快指针所走的路程是慢指针的两倍。
假设起点到入环口的距离是L，圆环的长度为C，入口点到相遇点的距离为x，这时通过分析就可以列出一个等式。

快指针的路程是慢指针的二倍

2(L+X)=L+n( C )+X
可得
L+X=n( C )
L=n( C ）-X;

设置两个指针，第一个指针从起始位置出发，另一个指针从相遇点出发，他们就会在环的入口处相遇。
套用第一道题的思路，快慢指针相遇时找到相遇点，在设置两个指针分别出发，直到相遇，如果没有环的话就返回NULL;
代码如下
    struct ListNode*fast=head;struct ListNode*slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){struct ListNode*meet=slow;while(head!=meet){head=head->next;meet=meet->next;}return meet;}}return NULL; } 
提交后顺利通过。

环形链表的约瑟夫问题
链接：
环形链表的约瑟夫问题

要使用单向链表实现。
分析题目，构建一个链表，依次储存节点的位置，然后找到链表的尾，尾的next等于头节点，这样一个环形链表就构建成功了。
从第一个节点开始往后走m-1步（数数时为m，因为第一个节点数1，所以往后走m-1到达目标节点），保存这个节点的next，将起始位置更改为该next，然后从新的起始位置继续往后边数，直到删除到只剩最后一个节点为止，假设这个节点为hei，那么循环结束的条件就是hei->next==hei，判断条件就是hei->next!-hei。

要注意
看代码，讲解很详细

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef struct ListNode
{int val;struct ListNode* next;
}LN;LN* Initnode()
{LN* head = (LN*)malloc(sizeof(LN));head->next = NULL;head->val = 0;return head;
}LN* GetNewnode(int x)
{LN* newnode = (LN*)malloc(sizeof(LN));newnode->next = NULL;newnode->val = x;return newnode;
}
void Pushnode(LN* head, int x)
{assert(head);LN* pre = head;while (pre->next){pre = pre->next;}pre->next = GetNewnode(x);
}void Popnode(LN*head,LN* node)
{LN* cur = head;while (cur->next != node){cur = cur->next;找到要删除的节点的前一个}LN* next = node->next;cur->next = next;free(node);node = NULL;
}int main()
{int m, n;scanf("%d %d", &m, &n);//建立链表LN* head = GetNewnode(1);//第一个编号为1for (int i = 2; i <= m; i++){Pushnode(head, i);//建立链表}//找尾LN* cur = head;while (cur->next != NULL){cur = cur->next;}cur->next = head;//环形链表弄完//数数删位LN* hei = head;while (hei->next != hei){for (int i = 1; i < n; i++)//因为移动三步，是移动量两次。{hei = hei->next;}LN* pop = hei;//找到要删除的节点pophei = hei->next;//更换hei的位置Popnode(hei,pop);//删除pop。}printf("%d ", hei->val);//打印留下的节点的数值。return 0;
}