文章目录 前言环形链表题目描述思路正确代码 环形链表2题目描述正确代码思路讲解 复制带随机指针的链表😫暴力解法思路讲解正确代码巧方法正确代码 结尾

前言

本次题目包括环形链表(力扣简单) 环形链表2(力扣中等) 复制带随机指针的链表(力扣中等)

环形链表

连接

题目描述

及判断一个单链表内是否带环即可如果带环就返回true不带环就返回false. 我们使用快慢指针来解决这个问题

思路

快慢指针 定义fast和slow,fast一次跳两个节点,slow一次跳一个节点 让fast去追赶slow就好 如果fast先进入环内循环等到slow进入环内后fast如果是带环的就一定可以追上slow如果不带环就通过if判断条件结束进程就好👍

正确代码 bool hasCycle(struct ListNode *head) { if(head==NULL) { return false; }//head为空直接false struct ListNode *fast = head->next; struct ListNode *slow = head; while(fast != slow) { if(fast==NULL||fast->next==NULL||slow == NULL) { return false; }//检测fast和slow fast = fast->next->next; slow = slow->next; } //循环结束后返回true. return true; } 环形链表2

力扣中等(这道题主要是找规律和公式)连接

题目描述

对上一题进行了升级,我们要找到环形链表的节点.

正确代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { if(head == NULL) { return NULL; } struct ListNode *slow = head; struct ListNode *fast = head; while(fast&&fast->next) { fast = fast->next->next; slow = slow->next; if(fast==slow) { struct ListNode *meet = slow; struct ListNode *start = head; while(start!=meet) { start = start->next; meet = meet->next; } return meet; } } return NULL; } 思路讲解

步骤

首先判空通过快慢指针来判断是否为带环链表追赶上就进入if条件句内if条件内通过fast的速度是slow的二倍推出的距离相同得出代码即可得出meet(主要讲解) 前三步不需要讲,都在代码里了. 第四步讲一下如何推断的距离相同以及那两段的距离相同👍 开始: 首先我们需要表达出fast和slow各自走的路程大小(画图理解较好)—分两种情况

我直接将两种情况融合成为一种情况好了🤪

情况一在slow进圈前fast一直在转圈转了n圈 情况二在slow进圈前fast没有转圈也就是fast只转了2圈👍

情况一包括了情况二,情况二只是情况只是情况一的特殊情况而已👍. (没想到我也能跟别人讲数学知识=-=明明只是数学渣渣)

好 我们就讲情况一好了😜. 通过图来讲 好一些. (注:下图是fast已经追赶上slow的情况) (舒文的闲话: 至于为啥要以fast和slow相遇时的情况作图讲解其实也很简单,因为我们就只能得到fast和slow相遇时的情况😜.)

我们先来找他们的关系式吧.

slow作为慢指针它一定是不会转两圈及以上的因为fast会追上它而🔆fast如果在slow没进环之前是有可能已经转了n圈🔆了我们再通过fast走的路程是slow的二倍即可得到一下表达式 2L+2X = L+X+nC 移动一下可以得到以下式子 L = nC-X. 我们让一个变量从头走,让另一个变量从fast和slow相遇的地方走,当他俩相同时我们就得到了交点👍. 这也是我代码所实现的 struct ListNode *meet = slow; struct ListNode *start = head; while(start!=meet) { start = start->next; meet = meet->next; } return meet;

代码思想不难主要是公式的推导.希望大家可以看懂😜.

复制带随机指针的链表😫

实话实说,这倒是我进入数据结构之后遇见的最难的题了😫.

暴力解法

暴力的解法一定是不如巧方法效率高，但是这种方法还是很锻炼人的思想的，比如我就在一个野指针里载了一个下午🤣。

思路讲解 struct Node* copyhead = (struct Node*)malloc(sizeof(struct Node));//复制链表的头 struct Node* prev = copyhead;//用于开辟复制链表的变量后续不用了 struct Node* cur = head->next;//从第二个空间开始复制 copyhead->val = head->val; copyhead->next = NULL; //解决val和链表空间 while(cur != NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; prev->next = copy; prev = copy; cur = cur->next; copy->next = NULL; }

首先头指针判空就不赘述，上述代码主要是为了给我们复制链表空间，并把val付给我们的拷贝空间。值得注意的是 上图的置空其实非常关键，如果不置空就会得到 心脏骤停😢😢😢。所以链表末尾置空大家一定要重视起来啊！！！！！！😢 短短的两行置空让舒文痛失一个下午的学习时光😢。

//解决随机指针问题 int num = 0;//用于下标表达 struct Node* copycur = copyhead; cur = head; struct Node* tmp = head;//用于寻找random while(cur != NULL&&copycur!=NULL) { num = 0; if(cur->random == NULL) { copycur->random = NULL; } else { tmp = head; num = 0; while(tmp != cur->random) { tmp = tmp->next; num++; } tmp = copyhead; while(num) { tmp = tmp->next; num--; } copycur->random = tmp; } copycur = copycur->next; cur = cur->next; } return copyhead;

主要部分就是这块解决随机指针的问题了，我使用的计数器的方法，用num充当类似数组中下标的作用。通过遍历原链表中random指向的下标位置，我们就可以在我们拷贝数组哪里也让他指向相同下标的链表节点位置。然后让原链表向下移动，拷贝链表向下移动即可

结束。 暴力求解也是很有意思的解法大家可以试试哦~

正确代码 /** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { if(head == NULL) { return NULL; } struct Node* copyhead = (struct Node*)malloc(sizeof(struct Node));//复制链表的头 struct Node* prev = copyhead;//用于开辟复制链表的变量后续不用了 struct Node* cur = head->next;//从第二个空间开始复制 copyhead->val = head->val; copyhead->next = NULL; //解决val和链表空间 while(cur != NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; prev->next = copy; prev = copy; cur = cur->next; copy->next = NULL; } //解决随机指针问题 int num = 0;//用于下标表达 struct Node* copycur = copyhead; cur = head; struct Node* tmp = head;//用于寻找random while(cur != NULL&&copycur!=NULL) { num = 0; if(cur->random == NULL) { copycur->random = NULL; } else { tmp = head; num = 0; while(tmp != cur->random) { tmp = tmp->next; num++; } tmp = copyhead; while(num) { tmp = tmp->next; num--; } copycur->random = tmp; } copycur = copycur->next; cur = cur->next; } return copyhead; } 巧方法

巧方法的思路其实也是比较简单的. 先创建链表并附在原链表的后面. 如图: 这也是下面代码所实现的👍

struct Node* cur = head; while(cur!=NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next; }

记得把新创的空间放在原链表后记得让cur走两步才能到下一个原链表元素上

然后对cur进行赋值成head让他继续搞随机指针🤪. 先看看代码吧

cur = head; while(cur != NULL) { if(cur->random == NULL) { cur->next->random = NULL; cur = cur->next->next; } else { cur->next->random = cur->random->next; cur = cur->next->next; } }

这串代码其实思想也十分简单原本链表的random所指向的位置的下一位及next就是我们想让我们拷贝链表的random指向的位置🤪.

最后一步,将链表拆下来. 这一步最难搞了😫 将copy的链表拆下时要注意一下细节

cur = head; struct Node* copyhead = head->next; struct Node* copytail = copyhead; if(copyhead->next==NULL) { return copyhead; } while(cur!=NULL) { struct Node* copy = cur->next; struct Node* curnext = copy->next; copytail->next = copy; copytail = copy; cur->next = curnext; cur = curnext; }

我们将他拆下时要用copyhead来保存头部位置对要拆下的部分使用类似于尾插的形式,然后我们使用变量保存的方式将原链表恢复成原本的模样.

好这样整体思路就确定下来了🤪.

用copy来确定要搬用的空间的位置. 用curnext来确定原链表的的下一个空间的位置. copytail用于尾插时的控制.

但是这样的循环解决不了单单一个空间的情况不过这种情况我们一个if就可以解决了.

正确代码 /** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { if(head==NULL) { return NULL; } struct Node* cur = head; while(cur!=NULL) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next; } cur = head; while(cur != NULL) { if(cur->random == NULL) { cur->next->random = NULL; cur = cur->next->next; } else { cur->next->random = cur->random->next; cur = cur->next->next; } } cur = head; struct Node* copyhead = head->next; struct Node* copytail = copyhead; if(copyhead->next==NULL) { return copyhead; } while(cur!=NULL) { struct Node* copy = cur->next; struct Node* curnext = copy->next; copytail->next = copy; copytail = copy; cur->next = curnext; cur = curnext; } return copyhead; } 结尾

机器人🤤,嘿嘿,.🤤.舒文最爱机器人了🤤.

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。