A dirty cheating solution (O(n) time, O(1) space)


  • 3
    B

    This low-down, double-crossing, underhanded solution works as long as the val's stored in the nodes are not too big. It shifts the nodes' int values by one or two bits (one bit if the node is on one list, two bits if the node is on two lists). This lets us sneakily store O(n) amount of memory without actually allocating any more than O(1) beyond what's already been allocated before the function was called.

     public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode x,y;
        
        for ( x = headA; x != null; x = x.next )
          x.val *= 2;
        for ( x = headB; x != null; x = x.next )
        {
          x.val *= 2;
          x.val += 1;
        }
        for ( y = headA; y != null; y = y.next )
        {
          if ( y.val % 2 == 1 )
            break;
        }
        for ( x = headB; x != null; x = x.next )
          x.val /= 2;
        for ( x = headA; x != null; x = x.next )
          x.val /= 2;
          
        return y;
    }
    

    }


  • 0
    E

    How can you know that val is not originally 0


  • 0
    E

    Tricky!

    The question indeed didn't forbid you to change the value of the Nodes.... Very creative lol


Log in to reply
 

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