Linked List Cycle II

文章目录

1. 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?

思路

设置快慢指针，快指针每次走两步，慢指针每次走一步，若快慢指针相遇，则证明有圈存在。假设慢指针和快指针相遇时，慢指针走了L步，则快指针走了2L步，圈长假设为R步。则2L-L=NR,L=NR。可证明慢指针从头结点出发，快指针从相遇点出发，快慢指针每次都走一步，则再次相遇的时候在圈的起始点。

证明：

当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环n圈(1<=n)。假设slow走了L步，则fast走了2L步，L=n*r;

设整个链表长S步，环入口点与相遇点距离为L1，起点到环入口距离为L0，则L0+L1=nr=(n-1)r+r=(n-1)r+S-L0,L0=(n-1)r+(S-L0-L1)。
S-L0-L1为相遇点到换入口点的距离。于是可知，从起点到环入口的距离等于n-1圈内环+相遇点到环入口。

解题

c++版

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next)
            return NULL;
        ListNode *slow=head,*fast=head;
        while(fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(fast==slow){
                slow=head;
                while(slow!=fast){
                    slow=slow->next;
                    fast=fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};

python版

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a list node
    def detectCycle(self, head):
        if not head or not head.next:
            return None
        slow=fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                break
        if slow==fast:
            slow=head
            while slow!=fast:
                fast=fast.next
                slow=slow.next
            return slow
        return None