♥♥♥我猜你最喜欢的链表系列之环形链表的理解及练习♥♥♥
♥♥♥我猜你最喜欢的链表系列之环形链表的理解及练习♥♥♥
一·环形链表的判断：
这里我们要知道链表可以分为带环与不带环，不带环的话它一直访问下去就会走到NULL，而带环的话它就会成为一个死循环。
带环：
那么我们接下来就来分析如何判断一个链表是否带环呢？这里我们还是用了一个快慢指针来判断：下面先展示一下代码：
bool hasCycle(struct ListNode *head) {
struct ListNode *fast=head;
struct ListNode *slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
return true;
}
}
return false;
}//这里判断是否带环用了bool类型下面我们来画图分析一下：
这样我们可以看出来当慢指针进入这个环后，我们就可以想象成为一个快指针追慢指针的问；这样之后慢指针每次都走一步，而快指针是两步，它们一开始认为快指针比慢指针慢有一定距离然后它们的相对距离就会变成每次-1；这样肯定能在环内某个位置相遇，因此我们可以拿着个方法来判断链表是否带环。
这里我们来一道例题：
按照快慢指针解题就可以通过；代码如上。
二·环形链表快慢指针追及问题分析：
这里我们来就这个问题简单分析一下，如果我们快指针走三步，慢指针走两步的话，结果又会是怎么样呢？
这样我们就简单分析了快指针走三步的情况，当然还有可以走更多步，那就更加复杂了，暂且讨论于此。
三·返回入环后第一个节点：
对于这个题，有两种解题思路：
第一种：就是我们可以确定如果快指针走的步数为2，慢指针走的步数为1；那么，当两者相遇，的位置为meet，然后我们让起始点指针和meet分别走一步，那么两者相遇时候一定是入环第一个节点处：下面证明一下：
下面根据第一种方法的思路完成代码：
//解法一：
// struct ListNode *detectCycle(struct ListNode *head) {
// struct ListNode *fast=head,*slow=head;
// while(fast&&fast->next){
// fast=fast->next->next;
// slow=slow->next;
// if(slow==fast){
// struct ListNode *meet=slow;
// while(head!=meet){
// meet=meet->next;
// head=head->next;
// }
// return meet;
// }
// }
// return NULL;
// }第二种：这种便是我们的简单思路；也就是将其看成有公共节点的俩个链表求公共节点问题：
下面思路清晰，于是我们来写法二的代码：
struct ListNode *getbothnode(struct ListNode *a,struct ListNode *b){
struct ListNode *headA=a;
struct ListNode *headB=b;
int len1=0;
int len2=0;
struct ListNode *cur1=NULL;
struct ListNode *cur2 =NULL;
while(headA){
cur1=headA;
headA=headA->next;
len1++;
}
while(headB){
cur2=headB;
headB=headB->next;
len2++;
}
if(cur1!=cur2){
return NULL;
}
int gap=abs(len1-len2);
struct ListNode *longlist=NULL;
struct ListNode *shortlist=NULL;
if(len1>len2){
longlist=a;
shortlist=b;
}
else{
longlist=b;
shortlist=a;
}
while(gap){
longlist=longlist->next;
gap--;
}
while(shortlist!=longlist){
longlist=longlist->next;
shortlist=shortlist->next;
}
return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast=head,*slow=head;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(slow==fast){
struct ListNode *meet=slow;
struct ListNode *newhead=meet->next;
meet->next=NULL;
struct ListNode *r= getbothnode(newhead,head);
meet->next=newhead;
return r;
}
}
return NULL;
}如果我们数学推算不好的话因此只能选择法二来解决此道题，那么代码量也就偏多了。
四·随机链表的复制：
下面我们解一道关于链表深拷贝的题：
解这道题我们分为三步：1.将新链表和原链表建立指针指向的关系。2.布置好新链表的random指针指向的位置。3.将新链表和旧链表的指针连接关系拆开，将新链表连接起来。
第一步解析：
第二步解析：
第三步解析：
这样我们就把思路整理了一遍，接下来来完成题解：
struct Node* copyRandomList(struct Node* head) {
struct Node*cur=head;
while(cur){
struct Node*copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
copy->next=cur->next;
cur->next=copy;
cur=copy->next;
}
//第一步：将旧链表和新链表建立关系
cur=head;
struct Node*copy=NULL;
while(cur){
copy=cur->next;
if(cur->random==NULL){
copy->random=NULL;
}
else{
copy->random=cur->random->next;
}
cur=copy->next;
}
//第二步：将新链表的random指针布置好
cur=head;
struct Node*copyhead=NULL,*copytail=NULL;
while(cur){
copy=cur->next;
if(copytail==NULL){
copyhead=copytail=copy;
}
else{
copytail->next=copy;
copytail=copy;
}
cur=copy->next;
}
//第三步：将新链表每个节点连接起来
return copyhead;
}腾讯云开发者
