Stupid and short c++ solution without any list cycles O(N) time, O(1) memory


  • 22
    A

    Just store addition information in 'next' pointers.
    It's work because memory alignment

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        for (ListNode *cur = headA; cur;) {
            unsigned long *ptr = (unsigned long *)&cur->next;
            cur = cur->next;
            *ptr |= 1;
        }
    
        ListNode *result = nullptr;
        for (ListNode *cur = headB; cur; cur = cur->next) {
            unsigned long ptr = (unsigned long)cur->next;
            if (ptr & 1) {
                result = cur;
                break;
            }
        }
        
        for (ListNode *cur = headA; cur; cur = cur->next) {
            unsigned long *ptr = (unsigned long *)&cur->next;
            *ptr &= (~0ULL << 1);
        }
    
        return result;
    }

  • 1
    S

    I like the solution. Nice trick of taking advantage of the alignment. 1 up vote from me. Only caveat is this list can't be use in real world by any other thread as the pointers are being modified.


  • 0
    C

    awsome && crazy, ++up


  • 0
    M

    nice trick!! I was thinking of a way to mark the elements but cannot do it in O(1) memory. This trick is really awesome. ++


  • 0
    R

    nice solution. However, this can be only performed in C++. Java can not : (


  • 0
    C

    niubility!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


  • 0
    M

    A short but intricate version of your idea. The code in the comments can replace their next line. If replaced, VS2010 would give the same right answer, but OJ would give a runtime error.

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) {
            return NULL;
        }
        
        ListNode** pp = &(headA->next);
        while ((*(long*)pp |= 1L) != 1L) {
            // pp = (ListNode**)((char*)*pp - 1 + sizeof(int));
            pp = &(((ListNode*)((char*)*pp - 1))->next);
        }
    
        ListNode* q = headB;
        while (q != NULL && !((long)(q->next) & 1L)) {
            q = q->next;
        }
    
        pp = &(headA->next);
        while ((*(long*)pp &= -2L) != 0L) {
            // pp = (ListNode**)((char*)*pp + sizeof(int));
            pp = &((*pp)->next);
        }
    
        return q;
    }

  • 0
    S

    I don't know C++. But I think this must be a very nice solution. Could anybody explain the idea more? Thanks!


  • 0
    A

    I use idea of memory alignment. so, on modern 64-bit systems allocators return memory, divided by 16, and it means, that last 4 bits must always be zero
    And we can store some additional data right in pointers.

    The same idea in linux kernel (look at unsigned long __rb_parent_color field):
    https://github.com/torvalds/linux/blob/master/include/linux/rbtree.h


Log in to reply
 

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