乐平市建设局网站,深圳画册设计团队,wordpress 评分,番禺人才网前言#x1f338;各位读者们好#xff0c;本期我们来填填之前留下的坑#xff0c;继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是#xff0c;我们今天的题目主要是于环形链表有关#xff0c;下面让我们一起看看吧。#x1f4bb;本期的题目有#xff1a;环…前言各位读者们好本期我们来填填之前留下的坑继续来讲解几道和链表相关的OJ题。但和上期单向链表不一样的是我们今天的题目主要是于环形链表有关下面让我们一起看看吧。本期的题目有环形链表、环形链表II、求环形链表环长环形链表a.题目b.题解分析第一种方法我们可以遍历链表使用哈希表来保存已经经过的结点。每次经过一个结点时通过哈希表判断结点是否被访问过如果有则说明存在环如果没有则继续访问下一结点以此循环直到遍历完整个链表。这样的时间复杂度为O(N)空间复杂度为ON不满足题目的进阶解法。第二种方法我们可以使用上期学习的快慢指针法。定义步长为2的快指针和步长为1的慢指针遍历链表。我们假设链表如果存在环则快慢指针在某一时刻一定会在环内相遇而如果不存在环由于快指针速度比慢指针快因此它们永远无法相遇。动态效果如下我们可以看到如果链表存在环时当慢指针进入环中后快指针就会开始绕环追逐慢指针。我们假设此时快慢指针距离为n由于v(快)-v(慢)1则每次行动快慢指针的距离就会缩短1行动n次后快慢指针一定就会相遇。因此我们可以通过判断是否相遇来判断是否有环。c.AC代码struct ListNode
{int val;struct ListNode* next;
};
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 (fast slow){return true; //相遇}}return false; //没有相遇、没有结点、只有一个结点且非循环不存在环}d.拓展思考通过以上例子我们知道速度差为1的快慢指针可以用来判断链表是否存在环。那么速度差为2的是不是也可以用来判断呢速度差为3的呢为n的呢我们来分析一下当快慢指针的速度差为2时假设慢指针进入环时快指针与其距离为n环的总长为m如下由于它们的速度差为2则每次行动后nn-2。我们很容易发现如果n为偶数时当行动次后快慢指针就会相遇但是当n为奇数时最后快慢指针就会错过进入下一轮追赶中。而在第二轮追赶开始时快慢指针距离为m-1假如m-1又是奇数则本轮又会错过进而进入第三轮追逐。然后第三轮开始时依旧相距m-1又会错过以此反复......最后永远不会相遇史上最遥远的距离无非就是我在你身旁你却不理不睬因此使用速度差为2的快慢指针不能保证是否可以判断出某个链表是否存在环速度差为3为n的同理。环形链表 II✈a.题目b.题解分析我们同样可以在上一题的基础上使用快慢指针来求解。我们假设链表头到环入口的长度为S环的长度为C。当慢指针走到环入口此时快指针的位置和慢指针的位置关系如下我们假设此时快慢指针的距离为L这里可能有读者有疑问快指针是慢指针速度的2倍那L的大小不应该是S吗实际上当slow到达环入口时fast可能已经绕环n圈了所以fast实际走过的长度共为SnCL()。由此我们可以得出SnCL2S即LS-nC。在这之后快指针开始追逐慢指针我们假设在如下位置相遇假设共进行了D次追逐才追上了慢指针由快指针比慢指针快一倍可以得出以下关系因此相遇点到快指针最初位置的距离为S-nC-D由此可以得出相遇点到环结点的距离为S-nC-DDS-nC,如下至此我们发现链表头到环入口的距离S与相遇点到环入口的距离S-nC相差n个环的长度。由此我们算法的思路是起初快指针速度为2慢指针速度为1如果快慢指针没有相遇则返回NULL代表不存在环如果相遇了我们就让其中一个指针重新指向链表头并使两个指针的速度都为1一直前进直到它们相遇相遇的位置一定为环的位置。这是因为从相遇点走S步后的位置与走S-nC步后的位置一致。c.AC代码struct ListNode {int val;struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode* fast head;struct ListNode* slow head;while (fast fast-next) //当到达或即将到达链表尾时退出循环{//快慢指针移动fast fast-next-next;slow slow-next;if (fast slow) //相遇存在环{//两个指针找环入口slow head;while (slow!fast){slow slow-next;fast fast-next;}return slow;}}return NULL;//没有相遇、没有结点、只有一个结点且非循环不存在环,返回空} 求环形链表的环长a.题目给定一个链表的头节点 head 返回链表环中环的长度。 如果链表无环则返回 0。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。b.题解分析法一我们同样可以先使用快慢指针判断链表是否存在环当二者第一次相遇时说明链表存在环。而当快慢指针相遇后我们再次让快慢指针进行追逐战此时它们之间的距离为环长C由于每次追逐它们的距离都会缩短1因此我们可以定义一个计数器count记录第二次相遇时所追逐的次数即为链表的环长。具体过程如下c.AC代码 struct ListNode {int val;struct ListNode* next;};
int CycleLength(struct ListNode* head)
{struct ListNode* fast head;struct ListNode* slow head;while (fast fast-next) //当到达或即将到达链表尾时退出循环{//快慢指针移动fast fast-next-next;slow slow-next;if (fast slow) //第一次相遇存在环{//统计第二次相遇所追逐的次数int count 0;do{fast fast-next-next;slow slow-next;count;} while (fast ! slow);//相遇了返回追逐次数即为环长return count;}}//不存在环返回0return 0;} 以上就是本期的全部内容啦制作不易能否点个赞再走呢
