双指针算法之快慢指针(一)：力扣【判断链表是否有环】leetcode-141、142

一、简介：什么是快慢指针？

快慢指针，顾名思义，无非就是设置一个快指针，一个慢指针，初始化的时候，快指针和慢指针都指向链表的头结点，前进的时候一个在前一个在后，结合起来可以十分巧妙的解决链表中的一些问题；

看完本文可以解决leetcode141题(简单)以及leetcode142题(中等)。
双指针算法之快慢指针(二)：力扣【寻找链表的第N个点】leetcode-876、19

二、典例一：判断链表是否有环

这个应该属于链表算法的经典的操作了，如果一个单链表有环，一个指针是判断不出来的，因为链表尾部和头部"链接"在一起，形成了一个死循环。

boolean hasCycle(ListNode head) {while (head != NULL)head = head.next;return false; }

如果使用一个指针：上述的代码，如果没有环的话，head 指针最后就会走到NULL,就会返回 false。到那时如果链表是有环的，就麻烦了，head会在循环中一直出不来的，自然不会有结果~
但是，如果设置快慢两个指针，快指针走到null的时候，就可以得知这个链表是没有环的；如果快慢指针相遇了，说明快指针肯定已经走了几圈了，这个链表肯定是有环的。
比较经典的就是leetcode的141题

1、题目描述：

2、思路以及代码

只要快慢指针相遇，说明是有环的,所以我们这里设置快指针 fast 一次走两步，慢指针 slow一次就一步；

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool hasCycle(ListNode *head) {ListNode *fast,*slow;fast = slow = head; // 初始都头节点的位置while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) { // 相遇了return true;}}return false;} };

三、典例二：判断链表中是否有环，有环就返回环的起始位置

刚刚的快慢指针判断链表是不是有环其实还是很好理解的，但是进一步提升的话，判断出来有环之后，返回这个环的开始位置, 不仅仅需要判断是不是有环，有环的话还有知道环是where 开始的。

比较经典的就是leetcode的142题

1、题目描述

2、题目分析

在这里，我们先回到上一题的解法，使用快慢指针去判断是不是有环，如果快慢指针相遇了，就是有环，那么，快慢指针相遇在哪一个点呢？这个点有什么特别之处吗？除了相遇的点，我们还应该注意到链表头结点，相遇点，环开始结点。
其实142题的核心，确实就在于分析一下这3个点，下面我们就来分析一下：

下图的声明：
O 是链表头结点
A 是环开始的点
B 是快指针和满指针相遇的点
K 是慢指针 slow 在快慢指针相遇之时走的路程，即推：快指针是 2 K
L(OA)是 从O 开始 第一次遇到 A 走的路长，就是下图蓝色部分
L(AB)是 从A 开始 第一次遇到 B 走的路长，就是下图红色部分
L环 是 从A 开始 再一次遇到 A 走的路长 其实就是k了
L(BA)是 从B开始 第一次遇到 A 走的路长。就是下图绿色部分

根据下图的计算，我们可以知道 L(OA）和 L(BA) 的长度是一样的。

由于 L(OA）和 L(BA) 的长度是一样的，所以我们在快指针 fast 和满指针 slow 相遇的时候，在B点相遇的时候，

1、快指针 fast 继续前进，速度和慢指针一样
2、慢指针 slow 返回链表头结点 O点，
3、快慢指针的速度保持一致，各自继续前进

那么，快慢指针下一次相遇的点是哪里？没错，就是 A 点，就是环开始的结点。

3、解题代码

由此，我们可以写出下面的伪代码：

ListNode detectCycle(ListNode head) {快慢指针初始化，都在头结点while (fast != null && fast.next != null) {快指针一次两步慢指针一次一步if (快指针 = 慢指针) {//即相遇 此时在 B 点慢指针回到头结点；while (slow != fast) {快慢指针继续走，一次一步；}return slow;}}return NULL; }

随后就可以写出全部的代码了：

class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode *fast,*slow;fast = slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {slow = head;while (fast != slow) {fast = fast->next; slow = slow->next;}return slow;}}return NULL;} };

总结

以上是生活随笔为你收集整理的双指针算法之快慢指针(一)：力扣【判断链表是否有环】leetcode-141、142的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。