青羊区城乡建设网站,05网全部答案数学,wordpress 调用侧边栏,网站设计网站维护欢迎来到 Claffic 的博客 #x1f49e;#x1f49e;#x1f49e; 前言#xff1a; 快慢指针指的是每次指针移动的步长#xff0c;是解决链表相关的题目的一大利器#xff0c;下面我将以例题的形式讲解快慢指针法。 目录
一. 链表的中间结点
思路#xff1a;
代码实… 欢迎来到 Claffic 的博客 前言 快慢指针指的是每次指针移动的步长是解决链表相关的题目的一大利器下面我将以例题的形式讲解快慢指针法。 目录
一. 链表的中间结点
思路
代码实现
二. 链表中倒数第k个结点
思路
代码实现
三. 判断链表中是否有环
思路
代码实现
四. 返回链表入环的第一个结点
思路
代码实现 一. 链表的中间结点
点我做题
思路
创建两个快慢指针 slow , fast 起始共同指向头节点slow 每次走一步fast 每次走两步当 fast 为空或 fast 的下一个结点为空时slow 即是中间节点的位置。
解释
由于 fast 每次走两步slow 每次走一步slow 总是落后 fast 整体一半的长度最终 slow 理应为中间结点。
结点数为奇数 最终 fast 在最后一个结点此时结束的标志为 fast-next NULL
结点数为偶数 最终 fast 在最后一个结点的下一个指向此时的结束标志为 fast NULL;
代码实现
struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow,*fast;slow head;fast head;while(fast fast-next){slow slow-next;fast fast-next-next;}return slow;
}
二. 链表中倒数第k个结点
点我做题
思路
同样创建两个快慢指针 slow , fast 起始共同指向头节点先让 fast 走 k 步再让 fast 和 slow 同时前进直到 fast 为空为止。
解释
先让 fast 走 k 步那么 fast 与 slow 之间就隔了 k-1 个结点fast 与 slow 同时前进直到 fast 为空时fast 与 slow 之间依然隔 k-1 个结点那就是倒数第 k 个结点。 代码实现
int kthToLast(struct ListNode* head, int k){struct ListNode* fast,*slow;fast slow head;if(head NULL){return NULL;}//fast 前进 k 步while(k--){fast fast-next;}//slow 与 fast 共同前进while(fast){slow slow-next;fast fast-next;}//注意返回的是整型数值return slow-val;
}
三. 判断链表中是否有环
点我做题
思路
快慢指针 slow , fast都从 head 开始slow 一次走一步fast 一次走两步如果 slow 和 fast 能相遇则链表有环。
解释
主要是证明 有环情况下两个指针一定能相遇
fast 比 slow 先进入环如图假设 slow 和 fast 的位置这两个指针之间差 N 步
由于 fast 每次走两步slow 每次走一步所以 slow 和 fast 之间的距离每次缩短 1 N - 1 N - 2 N - 3 ... 2 1 0 //此时两者相遇 证毕。
代码实现
bool hasCycle(struct ListNode* head) {struct ListNode* fast,*slow;fast slow head;while(fast fast-next){slow slow-next;fast fast-next-next;if(fast slow){return true;}}return false;
}
四. 返回链表入环的第一个结点
点我做题
思路
这里要先放一个结论
在链表有环的情况下一个指针在起始结点开始走另一个结点在相遇点开始走最终两个指针会在入环点相遇。
快慢指针 slow , fast都从 head 开始slow 一次走一步fast 一次走两步找到相遇点后再让 start 与 meet 同时前进两者相等的点即是入环点。
解释
自然要证明上边的结论 在这里我们设几个常量 L起始点到入环点的距离 X入环点到相遇点的距离 C环的周长。 已知条件 slow 走的距离L X fast 走的距离L n*C X (n 1) fast 走的长度是 slow 走的长度的 2 倍。 推导 fast 走的长度是 slow 走的长度的 2 倍 -- 2*(L X) L n*C X (n 1) 整理得L C - X (n - 1)*C (n 1). 对 L C - X (n - 1)*C (n 1) 的解释 C - X (n - 1)*C (n 1) 原本是 meet 到 innode 要走的所有可能距离
而 L C - X (n - 1)*C (n 1) 说明 start 到 innode 要走的距离与 meet 到 innode 要走的所有可能距离相等所以两者相遇的点一定是 innode.
代码实现
struct ListNode* detectCycle(struct ListNode *head) {struct ListNode* slow,*fast;slow fast head;while(fast fast-next){slow slow-next;fast fast-next-next;if(slow fast){struct ListNode* meet slow;struct ListNode* start head;while(meet ! start){meet meet-next;start start-next;}return meet;}}return NULL;
} 总结
快慢指针是解决链表问题的一大利器建议多画图理解掌握。
码文不易
如果你觉得这篇文章还不错并且对你有帮助不妨支持一波哦
