[LeetCode] Linked List Cycle II, Solution

Question :

　　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?
Anaylsis :
- 　　
  
  首先，比较直观的是，先使用Linked List Cycle I的办法，判断是否有cycle。如果有，则从头遍历节点，对于每一个节点，查询是否在环里面，是个O(n^2)的法子。但是仔细想一想，发现这是个数学题。
  
  如下图，假设linked list有环，环长Y，环以外的长度是X。
  
  现在有两个指针，第一个指针，每走一次走一步，第二个指针每走一次走两步，如果他们走了t次之后相遇在K点
  
  那么       指针一走的路是      t = X + nY + K        ①
  
  指针二走的路是     2t = X + mY+ K       ②          m,n为未知数
  
  把等式一代入到等式二中, 有
  
  2X + 2nY + 2K = X + mY + K
  
  =>   X+K = (m-2n)Y    ③
  
  这就清晰了，X和K的关系是基于Y互补的。等于说，两个指针相遇以后，再往下走X步就回到Cycle的起点了。这就可以有O(n)的实现了。
- from : http://fisherlei.blogspot.tw/2013/11/leetcode-linked-list-cycle-ii-solution.html

Code :

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode *detectCycle(struct ListNode *head) {

    if(!head) return NULL;

    struct ListNode* slow=head;

    struct ListNode* fast=head;

    while(fast && fast->next) {

        fast = fast->next->next;

        slow = slow->next;

        if (slow == fast) break;

    }

    if(!fast || !fast->next) return NULL;

    while (slow != head) {

        slow = slow->next;

        head = head->next;

    }

    return slow;

}

巴特西

[LeetCode] Linked List Cycle II, Solution

最新文章

热门文章