C++ O(n) method with O(1) space using inplace mark.


  • -1
    T

    Mark the visited nodes in "next" pointer by skewing the pointer for +1 byte.
    Recover the list before return.

    class Solution {
        int offset;//offset of 'head' pointer
        int size;//size of ListNode
    
        inline ListNode* mark(ListNode *p)
        {
            char *t=(char*)(p);
            t++;
            return (ListNode*)(t);
        }
    
        inline ListNode* unmark(ListNode *p)
        {
            char *t=(char*)(p);
            t--;
            return (ListNode*)(t);
        }
    
        inline bool ismarked(ListNode *p)
        {
            int t=*((int*)(&p))%size;
            return t!=offset;
        }
    
        //recover the marked list
        inline void recover(ListNode *p)
        {
            while(p && ismarked(p->next))
            {
                p->next=unmark(p->next);
                p=p->next;
            }
        }
    public:
        ListNode *detectCycle(ListNode *head) {
            if(head==NULL || head->next==NULL) return NULL;
            
            size=sizeof(ListNode);
            offset=*((int*)(&head))%size;
            
            ListNode *p=head,*q=head->next;
            while(q)
            {
                //find marked node, recover & return
                if(ismarked(q->next))
                {
                    recover(head);
                    return q;
                }
                
                //mark the node & move to next
                q=p->next;
                p->next=mark(p->next);
                p=q;
            }
            recover(head);
            return NULL;
        }
    };

Log in to reply
 

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