O(n) solution without using extra space or changing the original list


  • 2
    T

    my method is quite simple :
    1.to know wether there is a ring.
    2.get the size of the ring using two pointers..one takes a step while the other takes two steps every time..when they meet for the second time..we get the size of the ring.
    3.from the head of the list..find the node which gets back to itself after taking sizeOfRing steps..

    class Solution {
        public:
            ListNode *detectCycle(ListNode *head) {
                if(!hasCycle(head))
                    return NULL;
                ListNode * p1 = head;
                ListNode * p2 = head;
                int len;
                for(int i=0;i<2;++i)    //get the length of the ring
                {
                    len = 1;
                    p1 = p1->next;
                    p2 = p2->next->next;
                    while(p2 != p1)
                    {
                        ++len;
                        p1 = p1->next;
                        p2 = p2->next->next;
                    }
                }
                p1 = head;
                p2 = head;
                p2 = moveBy(len,p2);
                while(p1 != p2)
                {
                    p1 = p1->next;
                    p2 = p1;
                    p2 = moveBy(len,p2);
                }
                return p1;
            }
            ListNode* moveBy(int steps,ListNode * p)  //move given steps from p and return the new position
            {
                for(int i=0;i<steps;++i)
                {
                    p = p->next;
                }
                return p;
            }
            bool hasCycle(ListNode * head) 
            {
                if(!head)
                    return false;
                ListNode * p1 = head;
                ListNode * p2 = head;
                p1 = p1->next;
                if(!p1)
                    return false;
                p2 = p2->next->next;
                if(p1 == p2)
                    return true;
                while(p2 && p2->next && p1!=p2)
                {
                    p1 = p1->next;
                    p2 = p2->next->next;
                }
                if(p1 == p2)
                    return true;
                else
                    return false;
            }
        };

Log in to reply
 

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