Is there anybody could tell me how to solve this problem with a constant space?


  • 0
    Z

    Here is my accepted answer using C ++.As u can see, i use a O(n) space-complexity.I wonder what the O(1) space-complexity method is.Thanks.

    class Solution {
        public:
         ListNode *detectCycle(ListNode *head) {
             if (head == NULL)return NULL;
              ListNode *fast, *slow;
              map<ListNode*, bool> mp;
              mp.clear();
              fast = slow = head;
              int count = 0;
              fast = fast->next;
              while (fast != NULL){
                    if (!(count%2)){
                       mp[slow] = true;
                       slow = slow -> next;        
                    }      
                    if (mp[fast] == true)return fast;
                    fast = fast->next;
                    
                    count ++;
              }  
              return NULL;
        }
    };

  • 0
    S

    Look around this Category in our discuss.

    Here is a helpful answer.


  • 1
    R

    Here is how I did it. There're some comments in my code.
    Here are some of my thoughts of how to tackle this problem.

    1. understand how to detect cycle as in Linked List cycle (I) without returning pointer to the node in constant space. (faster and slower pointers)

    2. Think about where slower and faster pointer will meet if the linked list is a Circle, a degenerated case for cycle. (They will meet where they both start, the head)

    3. Generalized 2) by considering there are a few nodes that does not contribute to a circle.

       if(head==NULL) {
           return NULL;
       }
       // faster and slower pointers to find the node they meet
       ListNode *faster = head, *slower = head;
       while(faster->next && faster->next->next) {
           slower = slower->next;
           faster = faster->next->next;
           if(slower==faster) {
               // we have a circle
               // now use a third pointer pointing at head to walk at speed = 1, and slower pointer walk at speed = 1,
               // the point they meet is the node we want.
               ListNode* thirdWalker = head;
               while(slower!=thirdWalker) {
                   slower = slower->next;
                   thirdWalker = thirdWalker->next;
               }
               return slower;
           } else {
               continue;
           }
       }
       return NULL;

  • 3
    Q

    This is how I do it.

    1. 1.Set a two pointers slow and fast
    2.fast moves 2 steps a time and slow one step a time for the fist pass
    3. if fast or fast->next pointer is null, it is not a cyclic list, return NULL
    4. else, it is cyclic. 
    5. cycle until slow meets fast
    6. reset slow to the start of the list, head.
    7. move fast and slow both one step a time
    8. The time they meet again is the cycle's starting pointer. return either slow or fast pointer.
    class Solution {
    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            ListNode *fast,*slow;
            fast=slow=head;
            while (1){
                if (fast==NULL||fast->next==NULL) return NULL;
                fast=fast->next->next;
                slow=slow->next;
                if (fast==slow) break;
    
            }
            slow=head;
            while (slow!=fast){
                slow=slow->next;
                fast=fast->next;
            }
            return fast;
        }
    };

  • 0
    Y

    Regarding "8. The time they meet again is the cycle's starting pointer.", how do you know this? Is there an algorithm explaining this? Thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.