前言
本次题目包括环形链表(力扣简单)
环形链表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;
代码思想不难主要是公式的推导.希望大家可以看懂😜.
