这几道题目都比较类似,都是用快慢指针法(fast, slow pointers),所以放在一起说好了。

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

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

用两个pointers, 一个每次向前一步s_ptr->next,另一个向前两步s_ptr->next->next,如果跑出去了就说明没有cycle,否则它们必然会在一个node相遇,证明存在cycle。


class Solution {
public:
        bool hasCycle(ListNode *head) {
                if(!head) return false;
                ListNode* l1 = head;
                ListNode* l2 = head;
                ListNode* l3 = head;
        
                while(head->next && head->next->next && head->next->next->next)
                {
                        if(l1->next) l1 = l1->next;
                        else return false;
                        if(l2->next && l2->next->next) l2 = l2->next->next;
                        else return false;
                        if(l3->next && l3->next->next && l3->next->next->next)
                                l3 = l3->next->next->next;
                        else return false;
            
                        if(l1 == l2 || l2 == l3 || l1 == l3) return true;
                }
                return false;
        }
};
12ms

Linked List Cycle II

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?
找cycle的起点,一个O(n^2)的办法是用I里面的方法找到环中相遇点,然后将一个pointer放回head,每次这个pointer走一步,环里的绕一圈,如果相等那就是这个node为起点。


class Solution {
public:
        ListNode *hasCycle(ListNode *head) {
                if(!head) return NULL;
                ListNode* l1 = head;
                ListNode* l2 = head;
        
                while(head->next && head->next->next && head->next->next->next)
                {
                        if(l1->next) l1 = l1->next;
                        else return NULL;
                        if(l2->next && l2->next->next) l2 = l2->next->next;
                        else return NULL;
            
                        if(l1 == l2) return l1;
                }
                return NULL;
        }
        ListNode *detectCycle(ListNode *head) {
                ListNode* cycle = hasCycle(head);
                if(!cycle) return NULL;
                if(cycle == head) return cycle;
        
                ListNode* ptr = head;
                ListNode* cycleStart = cycle;
        
                while(ptr)
                {
                        do{
                                if(ptr == cycle) return ptr;
                                cycle = cycle->next;
                        }while(cycle != cycleStart);
                        cycle = cycleStart = cycleStart->next;
                        ptr = ptr->next;
                }
        }
};
72ms

这个题目其实是个数学题,可以证明:设进入cycle之前的长度为a(从head到cycle起点的距离),相遇点为b,则从b回到cycle起点的长度c等于从head到cycle起点的长度a(a=c)。
Prove:
慢指针走过的距离 s_slow=a+b, 快指针走过的距离 s_fast=a+b+c+b,s_fast = 2 * s_slow, 所以a=c。
代码就很好写了,先找到相遇点b,然后慢指针回head,快指针减速每次前进一个Node,最后找到相遇点就是了。


class Solution {
public:
        ListNode *hasCycle(ListNode *head) {
                if(!head) return NULL;
                ListNode* l1 = head;
                ListNode* l2 = head;
        
                while(head->next && head->next->next && head->next->next->next)
                {
                        if(l1->next) l1 = l1->next;
                        else return NULL;
                        if(l2->next && l2->next->next) l2 = l2->next->next;
                        else return NULL;
            
                        if(l1 == l2) return l1;
                }
                return NULL;
        }
        ListNode *detectCycle(ListNode *head) {
                ListNode* cycle = hasCycle(head);
                if(!cycle) return NULL;
                if(cycle == head) return cycle;
        
                ListNode* ptr = head;
        
                while(ptr != cycle)
                {
                        ptr = ptr->next;
                        cycle = cycle->next;
                }
                return ptr;
        }
};
12ms

Find the Duplicate Number
这个题目抽象过来其实就是个链表,只不过是用index作为链接方式。按照上面方法找到cycle起点,然后起点的前一个数字(也就是起点的index)就是那个重复的数字。因为假设有一个重复数字a,当第一次遇到a时候必然跳到nums[a],然后继续向前,直到遇到第二个a,再次返回nums[a]构成cycle。所以很自然的起点前一个就是重复数字。


class Solution {
public:
        int findDuplicate(vector<int>& nums) {
                int s_index, s_val, f_index, f_val;
                s_index = f_index = 0;
                s_val = f_val = nums[0];
        
                do
                {
                        s_index = nums[s_index];
                        f_index = nums[f_index];
                        f_index = nums[f_index];
                }while(s_index != f_index);
        
                s_index = 0;
                while(nums[s_index] != nums[f_index])
                {
                        s_index = nums[s_index];
                        f_index = nums[f_index];
                }
        
                return nums[s_index];
        }
};
12ms

Leave a Reply

Your email address will not be published. Required fields are marked *