LeetCode日记–Floyd判圈问题

发布于 2020-10-09  108 次阅读


碎碎念:八天小长假终于结束了。。2020年的假期都无了,一想到这事儿就有点难受。

PS.今天这道easy很有意思,想了好一会儿才想到O(1)空间复杂度的解法。

关于Floyd判圈问题的wiki链接在这儿。(里边儿除了讲找入口的部分,其他的都不错)

题目如下:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).


Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.


Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

题目延伸:

让你求环的长度,或者是求环最初的节点(就是Example1中的2节点)。

思路:

我一开始的思路就是很暴力地使用hashMap把遍历过的节点装在hashMap里面,每遍历到一个新节点就使用contains方法,若直到遍历完都没有contains那就说明这个链表无环。

但是看了官方题解我才发现,既然没有重复元素,那么为什么不直接用hashSet呢?(而且似乎HashSet也是基于HashMap实现的,add进入HashSet的时候就是用我刚刚手动实现的方式看是否有相同元素,然后加入HashSet)

那么后面就很简单了,(但是我没有存下来自己实现的代码,就直接使用官方代码了)

代码如下:

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

那么我们要如何实现常数级空间复杂度呢?

这时候就要使用Floyd cycle Detection Algorithm 的核心思想----双指针了。(双指针の奇妙使用增加了!.jpg)

很显然,如果一个链表有环的话,若两个从头出发,且速度不一样的指针必然会在环的某处相遇。因此我们只要一直遍历,在遍历结束时未相遇则无环,否则则是有环。

细节:

若是使用while判断的话,则一开始一个指针应该为head,另一个应该为head.next,但是这样初始化不利于后面我们找到环初始的节点,因此我们使用do-while进行判断,这样第一次循环时不判断,则可以都从head处起始。

代码如下:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null)
            return false;
        if(head.next ==null)
            return false;
        ListNode second = head;
        ListNode first = head;
        do{
            if(first == null)
                return false;
            first = first.next;
            second = second.next;
            // 如果first本身已经为null了,再往后移动则会出现空指针Error
            if(first!=null)
                first = first.next;
        }while(first!=second);
        return true;
    }
}

那么我们再更近一步想一下,怎么知道环的大小呢?其实很简单,当第一次相遇时两指针在环中位置一样,那么只需要让某个指针一直next直到再次相遇,并在过程中一直计数就可以了。

那么再深入地想一下,如何找到环的入口呢?

让我们看一个数学推导(来自LeetCode题解区):

s点为head
a点为环入口
b点为快慢指针相遇的点
x为头结点到环入口的距离
y为环入口到相遇点的距离
z为相遇点到环入口的距离
y+z为环的长度
计算环入口:
慢指针走的距离:x+y


快指针走的距离(假设在环内走了N圈):x+N(y+z) +y

快指针速度是慢指针的两倍:(x+y)2=x+N(y+z) +y

我们的目标: 圈数的n倍+z = ? 求出这个问号就可以就求出如何找到入口。

照着目标化简上式可以得到下面的结论:

结论:x=(N-1)(y+z)+z,即一个指针从头结点出发走x步,另一个节点从相遇点出发,绕着环走N-1圈和z步,最后两指针会在环入口处相遇。

作者:yim-6
链接:https://leetcode-cn.com/problems/linked-list-cycle-lcci/solution/python3-liang-chong-fang-fa-shi-xian-huan-lu-jian-/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

因此,这时候我们让其中一个指针回到head处,每次向后移动一步,再让另一个指针从相遇点开始移动,每次一步,最终两个指针会在环入口处相遇。

代码如下:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null)
            return null;
        if(head.next ==null)
            return null;
        ListNode second = head;
        ListNode first = head;
        do{
            if(first == null)
                return null;
            first = first.next;
            second = second.next;
            // 如果first本身已经为null了,再往后移动则会出现空指针Error
            if(first!=null)
                first = first.next;
        }while(first!=second);
        second = head;
        while(second!=first){
            second = second.next;
            first = first.next;
        }
        return second;
    }
}

彩蛋:

对于前面的是否有环的题目,还有一种贼逗的解法----面向测试用例的程序设计。

总之就是一直往下遍历,遍历10000次(题目给定的list range),如果还没有null就说明有环。

代码如下:

class Solution {
public:
    bool hasCycle(ListNode *head) {
        int cnt = 0;
        while(head){
            cnt ++;
            if(cnt > 10000)
                break;
            head = head->next;
        }
        return cnt > 10000 ? true : false;  
    }
};

你好哇!欢迎来到雷公马碎碎念的地方:)