C++ solution o(n) and o(1), Store access flag on the next field of ListNode


  • 1
    Z

    Link the end of ListA to the head of ListB. And start traverse from the head of ListA.
    if any node access more than one time, the node should be the intersection.

    As we know the memory address of one ListNode aligned at least by byte, so the lowest 3 bits are useless.
    We can use the lowest bit to store access flag.

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode *rev = headA;
            ListNode *p = rev;
            bool first=true;
            while (p && (((unsigned long)(p->next) & 0x1) != 0x1)){//if not access
                ListNode *t=p->next;
                p->next = (ListNode*)((unsigned long)(p->next) | 0x1); //set the access flag
                p=t;
                if (first && p==NULL){
                    first = false;
                    p=headB;
                }
            }
            ListNode *ans = p;
    
            //clear all access flag again
            p = rev;
            first=true;
            while (p){
                if (((unsigned long)(p->next) & 0x1) == 0x1)
                    p->next = (ListNode*)((unsigned long)(p->next) & ~0x1);
                p=p->next;
                if (first && p==NULL){
                    first = false;
                    p=headB;
                }
            }
            return ans;
    }

Log in to reply
 

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