自己做的网站放在服务器哪里,跨境电商营销,电子商务网站建设与管理目录,网络品牌推广的方法有哪些目录标题 前言环形链表的约瑟夫问题环形链表环形链表|| 前言 前面我们已经学习了关于单链表的一些基本东西#xff0c;今天我们来学习单链表的一个拓展——环形链表#xff0c;我们将用力扣和牛客网上的三道题目来分析讲解环形链表问题。
环形链表的约瑟夫问题 我们首先来看… 目录标题 前言环形链表的约瑟夫问题环形链表环形链表|| 前言 前面我们已经学习了关于单链表的一些基本东西今天我们来学习单链表的一个拓展——环形链表我们将用力扣和牛客网上的三道题目来分析讲解环形链表问题。
环形链表的约瑟夫问题 我们首先来看一道非常经典的题目——环形链表的约瑟夫问题。题目问题如下 输入5,2 输出3 说明 开始5个人 12345 从1开始报数1-12-2编号为2的人离开 1345从3开始报数3-14-2编号为4的人离开 135从5开始报数5-11-2编号为1的人离开 35从3开始报数3-15-2编号为5的人离开 最后留下人的编号是3 看着问题好像无从下手但只要掌握了链表的相关知识你也能拿捏环形链表题目。 这道题目说将n个人围城一个圈转换成链表也就是将n个节点串起来变成一个圈即将最后一个节点的next指针指向头节点这样环形链表就出现了。 当有5个人编号为2的离开流程如下 代码实现解析包含在代码中
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param n int整型 * param m int整型 * return int整型*///题目中没有给出链表我们首先要自己创建一个链表typedef struct ListNode ListNode;//给节点重命名ListNode* buyNode(int x)//建立新节点{ListNode* node (ListNode*)malloc(sizeof(ListNode));if(node NULL){exit (1);}node-val x;node-next NULL;return node;}ListNode* createCircle(int n){ListNode* phead buyNode(1);//首先创建头节点使后面的节点都能相连ListNode* ptail phead;for(int i 2;i n;i){ptail-next buyNode(i);ptail ptail-next;}ptail-next phead;//尾节点的next指向头节点使其成为环形链表return ptail;//返回尾节点}
int ysf(int n, int m ) {// write code hereListNode* prev createCircle(n);ListNode* pcur prev-next;//让尾节点的下一个节点也就是头节点赋给pcur让其成为数数的起始点。int count 1;//开始第一次数数记为1while(pcur-next ! pcur)//结束的标志是pcur-next pcur此时就只剩pcur这一个节点则跳出循环{if(count m)//如果pcur所对应的这个节点的值恰好为m则要删除这个节点在单链表中我们也讲过删除节点要怎么删除便不再多讲{prev-next pcur-next;free(pcur);pcur prev-next;count 1;//pcur往下走了一个节点要记得把count置为1继续下一次循环}else //不为m时prev指针和pcur指针都往下走一个且pcur对应的报数count要加加{prev pcur;pcur pcur-next;count ;}}return pcur-val;
}环形链表 学会的环形链表的约瑟夫问题下面来两道力扣中的环形链表问题 题目链接如下环形链表。题目如下 我们要判断一个链表看其是否有环先说结论我们可以利用快慢指针进行求解。顾名思义快慢指针就是存在两个指针一个走的快一个走的慢快指针一次走走两步或三步四步都可以慢指针一般走一步。 这道题中我们让快指针一次性走两边慢指针一次性走一步当慢指针进入环以后快指针开始追慢指针如果快指针能追上慢指针也就是两指针相遇则证明该链表带环。 代码如下
/**1. Definition for singly-linked list.2. struct ListNode {3. int val;4. struct ListNode *next;5. };*/
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slownode head, *quicknode head;//定义快慢指针while(quicknode quicknode-next)//快指针以及快指针指向的下一个节点不为空则一直循环{slownode slownode-next;//慢指针一次走一步quicknode quicknode-next-next;//快指针一次走两步if(quicknode slownode)//快慢指针相遇则链表带环{return true;}}return false;//为空跳出循环说明该链表不带环
}下面将解决大家的疑惑点
为什么快慢指针一定会相遇而不是会错过如何证明当慢指针走一步快指针走3步4步……又一定能追上相遇吗如何证明 这两个问题我们来一一解决。 首先是第一个问题为什么快慢指针一定会相遇而不是会错过如何证明。我们可以将快慢指针走的过程图画出来 所以当快指针一次走两步慢指针一次走一步时如果链表带环二者一定会在环内相遇这就证明解决了第一个问题 下面是第二个问题当慢指针走一步快指针走3步4步……又一定能追上相遇吗如何证明。 当慢指针一次走一步快指针一次走3步时证明如下 当slow进环时fast和slow的距离为n slow一次走一步fast一次走三步 则它们每追击一次距离缩小2 n是偶数n是奇数nnn-2n-2…………43210-1追上了错过了进行新一轮追击 如果n是奇数fast错过了slow此时fast到了slow前面一格假设环的长度为C则slow和fast是距离变为了C-1开始新一轮追击还是讨论C-1是偶数还是奇数的问题如果C-1是偶数就能追上如果C-1是奇数那永远不会追上。 根据以上分析我们可以得出结论
当n时偶数第一轮就能追上
当n时奇数时第一轮追击会错过二者的距离变成C-1C是环的长度 如果C-1是偶数即C是奇数那么下一轮就能追上相遇如果C-1是奇数即C是偶数那么永远追不上
看似我们已经讨论出了有追上和追不上的这两种情况但是追不上的情况即n是奇数C是偶数的情况真的会存在吗我们可以继续往下讨论 当slow进环时fast和slow的距离为n slow一次走一步fast一次走三步 我们就能发现fast走的距离是slow的三倍 根据这个关系可以列出等式 slow走的距离L fast走的距离Lx * cc-nslow进环时假设fast已经在环里面转了n圈 则得到等式3 * L Lx * cc-n 化简得到2 * L (x1) * c-n 2*L必定是偶数 根据上面得出的结论当n是奇数c是偶数时永远追不上 将其带入右边的式子得到x1*偶数 - 奇数此时得到的式子只能是奇数与左边不等则发现永远追不上的条件不成立。 根据以上一系列分析可以得出结论 当slow一次走一步fast一次走三步时若n是偶数则第一轮就能追上若n是奇数c是奇数时第二轮追上即无论如何一定能相遇追上。当fast一次走4步或者5步时也是同样的证明方法。
环形链表|| 这道题的环形链表是上一道题的进阶如果链表中有环则要返回入环的第一个节点没环则返回空题目链接如下环形链表|| 对于本题我们用到的是和上一题差不多一样的思路首先判断有没有环就用快慢指针发现有环要找到入环的第一个节点我们有两种办法解决
将快慢指针相遇时的节点我们记为meet节点然后让头节点和meet节点同时走每次都走一步当二者相遇时的节点就是进环时的第一个节点。将快慢指针相遇时的节点我们记为meet节点然后将meet节点与meet的下一个节点断开使其形成两条链此时就变成了求两条链表的相交问题代码写起来较为复杂
下面一一讲解 对于方法一 我们需要证明的是为什么让头节点和meet节点一起每次走一步当二者相遇的时候就是进环节点。 上一题我们通过画图找等式来解决为什么一定相遇这题我们同样可以通过画图找等式解决。 我们用快慢指针快指针一次走两步慢指针一次走一步 则快指针走的路程是慢指针的两倍 由图slow和fast相遇时距离进环时的一个节点为N slow走的距离LN slow指针在环内走不到一整圈因为当slow走一圈fast在环内走两圈肯定早就会相遇所以slow指针在环内只能走N的距离 fast走的距离Lx * C N slow进环前fast指针已经走了x圈 所以得到等式2 * (LN) L x * C N 化简得到L (x - 1)*C C - N (x - 1)*C是圈数 C - N 是meet节点与进环节点的距离二者相加刚好为L 这就是为什么头结点和meet节点每次同时走一步二者相遇时就是进环节点 代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode* fast head, *slow head;//给定两个快慢指针while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow)//相遇则带环{ListNode* phead head;ListNode* meet slow;//相遇节点置为meetwhile(phead ! meet){phead phead-next;meet meet-next;//头节点和meet节点每次走一步}return phead;//相遇返回其节点}}return NULL;//不带环返回空}对于方法二 我们要知道如何把环形链表断开使其成为两条链表并找到两条链表的相交节点即为进环节点。 将meet的下一个节点记为newhead并将其断开此时就有head和newhead两条链求这两条链表的相交节点即可。 代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//定义一个函数寻找两条链表的相交节点ListNode* l1 headA, *l2 headB;int a_count 1, b_count 1;while(l1-next){l1 l1-next;a_count;//给A链表长度计数}while(l2-next){l2 l2-next;b_count;//给B链表长度计数}//此时l1和l2都到达了两条链表的尾节点if(l1 ! l2)//如果二者不相等说明两条链表不想交{return NULL;}//到这说明两条链表尾节点相等链表相交int gap abs(a_count - b_count);//得到两链表节点个数的差值ListNode* fastnode headA, *slownode headB;//假定长链表为链表A短链表为链表Bif(b_count a_count)//如果B链表节点数多则交换{fastnode headB;slownode headA;}//就能保证fastnode一定是长的那个链表while(gap){fastnode fastnode-next;//先让长的链表走它们的差值gap--;}while(fastnode ! slownode){fastnode fastnode-next;slownode slownode-next;//两链表一起走相等了则为相交节点}return fastnode;
}
struct ListNode *detectCycle(struct ListNode *head) {ListNode* fast head, *slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){ListNode* phead head;ListNode* meet slow;//相遇节点置为meetListNode* newhead meet-next;//meet节点的下一节点作为新链表的头结点newheadmeet-next NULL;//将其断开return getIntersectionNode(phead,newhead);//返回两条链表的相交节点。}}return NULL;}方法二就到此结束代码比较长是因为设计到了两条链表相加节点的问题在力扣上也有此题目大家也可以下去做做链接如下相交链表。 本篇内容到此结束了关于链表大家要自己多想多画图多练习。感谢大家观看如果大家喜欢希望大家一键三连支持一下如有表述不正确也欢迎大家批评指正。
