环形链表（快慢指针）

题目

在leetcode上有两道关于环形链表的题，分别是：

• 给定一个链表，判断链表中是否有环。
• 给定一个链表，返回链表开始入环的第一个节点。

如上图所示，第一题你需要返回true，第二道题你需要告诉人家入环点为2。

思路

我的第一反应是哈希表，这样的时间复杂度可以控制在O(n)，但是空间复杂度也是O(n)。

具体的做法就是每遍历一个节点，就把它放在哈希表中去，如果遍历到NULL节点就是没有环，如果遍历到第一次在哈希表中存在的节点，那么就是有环，并且是第一个入环点。

为了优化空间复杂度，我想了许久，也看了点资料。

快慢指针法

定义两个指针，分别为slow和fast，一快一慢。起始点都是HEAD节点，以上图为例，就是节点3。

两个指针同时开始移动，fast指针每次移动两个位置，（3-> 0 -> 2）、slow指针每次移动一个位置，（3-> 2 -> 0）。

fast指针每走一步就拉slow指针1个位置，

假设开始节点HEAD距离入环点距离为N，当slow到达入环点的时候，其实快指针已经在环里面走了N的距离了，如果环的长度为K，那么以fast指针的视角来看，可以理解为slow指针在它前面K-N个位置（假设环足够大）。因为fast指针每走一步就拉slow指针1个位置，所以经过K-N个位置之后（慢指针的速度，快指针已经走了2（K-N）），快慢指针就会相遇。

上面的原理就可以解开问题一。

相遇之后fast和slow指针的位置为入环点后（K-N）个位置，也就是说他们再走N个位置将会到达入环点。而HEAD到达入环点的距离也正好是N，我们选取fast点把它指向HEAD节点，然后fast和slow同时开始移动（注意，fast和slow每次都移动一个位置）。经过N步之后，他们会同时到达入环点。

上面的原理就可以解开问题二。

用这种方式解答这道题时间复杂度为O(n)，空间复杂度为O(1)。

代码

问题一

public class Solution {
    public boolean hasCycle(ListNode head) {
      if (head == null || head.next == null) {
            return false;
        }

        ListNode slow = head;
        ListNode fast = head;

        boolean first = true;

        while (first || slow != fast) {

            if (fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
            first = false;
        }


        return true;
    }
}

问题二

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        boolean first = true;

        while (first || slow != fast) {

            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            first = false;
        }

        fast = head;

        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }
}

leetcode展示

最后

以上就是迷路冬天为你收集整理的环形链表（快慢指针）环形链表（快慢指针）的全部内容，希望文章能够帮你解决环形链表（快慢指针）环形链表（快慢指针）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。