首页 > ACM题库 > LeetCode > LeetCode-Linked List Cycle II[链表]
2014
11-19

LeetCode-Linked List Cycle II[链表]

Linked List Cycle II

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

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

标签: Linked List Two Pointers
分析

当fast与slow相遇时,slow肯定没有遍历完链表,而fast已经在环内循环了$n$圈($1 \leq n$)。假设slow走了$s$步,则fast走了$2s$步(fast步数还等于$s$加上在环上多转的$n$圈),设环长为$r$,则:
\begin{eqnarray}
2s &=& s + nr \nonumber \\
s &=& nr \nonumber
\end{eqnarray}

设整个链表长$L$,环入口点与相遇点距离为$a$,起点到环入口点的距离为$x$,则
\begin{eqnarray}
x + a &=& nr = (n – 1)r +r = (n-1)r + L – x \nonumber \\
x &=& (n-1)r + (L – x – a) \nonumber
\end{eqnarray}

$L – x – a$为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于$n-1$圈内环+相遇点到环入口点,于是我们可以从{head}开始另设一个指针{slow2},两个慢指针每次前进一步,它俩一定会在环入口点相遇。

代码1

//LeetCode, Linked List Cycle II
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode *slow2 = head;

                while (slow2 != slow) {
                    slow2 = slow2->next;
                    slow = slow->next;
                }
                return slow2;
            }
        }
        return nullptr;
    }
};

Java代码:

/**
 * 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(null == head || null == head.next) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(slow != null && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                slow = head;
                while(slow != fast){
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}

  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。