My C++ Accepted Solution with O(n) time and O(1) memory (72ms)


  • 34
    B

    The main idea of this solution is using the values of the intersecting nodes.

    First, calculate the total amount of value of nodes in listB.

    Second, add 1 to all the nodes in listA.

    Third, re-calculate the total amount of value in listB.

    If there exists some nodes intersecting, the re-calculated amount must be different from the previous one, otherwise, there is no any node intersecting. And we can also derive the first intersecting node through the difference between two amounts.

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *tmp = headB;
        int amoutB = 0,lengthB=0;
    
        //calculate the amount of values in listB and get the length of listB
        while (tmp!=NULL)
        {
            amoutB += tmp->val;
            lengthB ++;
            tmp = tmp->next;
        }
        
        //add 1 value to all nodes in listA
        tmp = headA;
        while (tmp!=NULL)
        {
            tmp->val++;
            tmp = tmp->next;
        }
        
        //re-calculate the amount of values in listB again
        tmp = headB;
        int newamoutB = 0;
        while (tmp!=NULL)
        {
            newamoutB += tmp->val;
            tmp = tmp->next;
        }
        tmp = headA;
    
        //subtract 1 from all the nodes in listA
        while (tmp!=NULL)
        {
            tmp->val--;
            tmp = tmp->next;
        }
        
        //if two amounts are the same, there is no node intersecting
        if(newamoutB==amoutB)
           return NULL;
        //the difference of two amounts means the number of intersecting nodes, 
        //we can get the first one by comparing it with number of nodes in listB
        else
        {
            tmp = headB;
            for(int i=0; i<lengthB-(newamoutB-amoutB);i++)
                tmp = tmp->next;
            return tmp;
        }
    
    }

  • 0
    M

    What will happen if some of the value's are minimum negative number of int and you decrease it?


  • 0
    J

    good point, also expected to exceed the upper or lower limitation


  • 0
    D

    I don't think this is a optimal solution because

    1. you changed the value of input. The problem only asked to not to change data structure, but I don't think changing the value is a good idea too.
    2. what if the value is not integer? like a string? If a linked list algorithm only works if all value are integer, this is not a really useful algorithm.
    3. the algorithm is actually similar to the method "record every item of A in list, check which one of B is in list", just you added integer together so it didn't take O(n) space, but it really depend on the trick of integer.

Log in to reply
 

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