(C/C++) 9ms with O(1) space, No Math, Pointer hack.


  • 0
    C

    This is just a simple hack.
    How it works?

    • Encode all passing node until NULL or encoded node - Make decision - Restore all encoded node.

    Why encoding works?

    • There are ranges of memory address in VAS restricted to system and PIO calls, so it is absolutely safe to use related bit to encode an pointer to a valid memory location.

    Some ralated reading:
    https://msdn.microsoft.com/en-us/library/windows/desktop/aa366912(v=vs.85).aspx

    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            //encoding
            ListNode* cur = head;
            while(cur && cur->next && !isPointerEncoded(cur->next)){
                encodePointer(cur->next);
               	cur = getDecodedPointerValue(cur->next);
            }
            
            ListNode* retVal = cur && cur->next ? cur : NULL;
            
            //decoding
            cur = head;
            while(cur && cur->next && isPointerEncoded(cur->next)){
                decodePointer(cur->next);
                cur = cur->next;
            }
            return retVal;
        }
    private:
        static const uint64_t MASK = (uint64_t)1 << (sizeof(ListNode*) * 8 - 1);
        
        void encodePointer(ListNode*& p)
        {
            uint64_t c = (uint64_t)p|MASK;
            p = (ListNode*)c;
        }
    
        void decodePointer(ListNode*& p)
        {
            p = getDecodedPointerValue(p);
        }
    
        ListNode* getDecodedPointerValue(ListNode*& p)
        {
            uint64_t c = (uint64_t)p&(~MASK);
            return (ListNode*)c;
        }
    
        bool isPointerEncoded(ListNode*& p)
        {
            return (uint64_t)p & MASK;
        }
    };
    

Log in to reply
 

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