2017-05-31 23:33:56 +0000   |     algorithm leetcode linked list two pointers   |   Viewed times   |    

题目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Follow up: Can you solve it without using extra space?

先确保用Map肯定能解

每个路过的元素都存入Map,第一个遇到两次的节点就是cycle的起始节点。时间复杂度 ,空间复杂度

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) { return null; }
        Set<ListNode> memo = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (memo.contains(cur)) { return cur; }
            memo.add(cur);
            cur = cur.next;
        }
        return null;
    }
}

结果

linked-list-cycle-two-1

不使用额外空间

Linked List Cycle的启发,可以用一个walker指针,每次前进一格,一个runner指针,每次前移两格,先确定有没有cycle。

如果确定有cycle,再用两个指针,一个cur指针从head节点开始遍历,另一个cycleCur指针一直在cycle里绕圈。cur每前进一格,cycleCur都绕一圈,探测有咩有遇到cur。什么时候遇到了,cur就是我们要找的cycle的起始节点。

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) { return null; }
        // find cycle
        ListNode mileStone = null;
        ListNode walker = head, runner = head;
        while (runner.next != null && runner.next.next != null) {
            runner = runner.next.next;
            walker = walker.next;
            if (runner == walker) {
                mileStone = runner; // find the cycle, milestone must be one of the node in cycle
                break;
            }
        }
        if (mileStone == null) { return null; } // do not have cycle
        ListNode cur = head, cycleCur = mileStone;
        while (true) { // assert: must have cycle
            do {
                if (cur == cycleCur) { return cur; }
                cycleCur = cycleCur.next;
            } while (cycleCur != mileStone);
            cur = cur.next;
        }
    }
}

结果

结果不理想。离银弹差好远。 linked-list-cycle-two-2

天才的数学计算法

这题的银弹比较神奇。需要一点数学上的洞察力。还是利用walkerrunner指针,walker每轮前进一步,runner每轮前进两步。当他们相遇的时候,说明有cycle存在。这时候记下walker一共走了k步,runner就走了2k步。然后假设

这时候我们就能得到两个等式,

2k - k = nr (1式)(runner在遇到walker之前,已经绕着cycle跑了n圈了)

k = s + m (2式)(就是walker从起始点跑到和runner相遇的地方的距离,可以肯定walker没有跑完一圈)

上面的两个等式(1)(2)能推出下面这个等式(3)

s = nr - m (3式)

这个等式就是说:一个指针cur从list起始点出发,另一个指针cycleCurrunnerwalker相遇点出发,两者每轮都前进一步,最后一定在cycle的首个节点相遇。

因为假设n=1的情况,s=r-m,就是说cycleCur只要继续跑完这一圈,回到cycle首节点,cur也正好到cycle首节点。如果n=2,就是cycleCur整整多跑一圈,但curcycleCur还是在cycle首节点相遇。事实上无论n=3,4,5,6,...curcycleCur总是在cycle首节点相遇,区别只是cycleCur多跑几圈而已。

代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) { return null; }
        // find cycle
        ListNode mileStone = null;
        ListNode walker = head, runner = head;
        int step = 0;
        while (runner.next != null && runner.next.next != null) {
            runner = runner.next.next;
            walker = walker.next;
            if (runner == walker) {
                mileStone = runner; // find the cycle, milestone must be one of the node in cycle
                break;
            }
            step++;
        }
        if (mileStone == null) { return null; } // do not have cycle
        ListNode cur = head, cycleCur = mileStone;
        while (cur != cycleCur) {
            cur = cur.next;
            cycleCur = cycleCur.next;
        }
        return cur;
    }
}

结果

结果非常好。但这个方法能不能推广到某一类问题,还值得观察。 linked-list-cycle-two-3