52ms in c++, with time o(n) space o(1)


  • 5
    T
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur_node_1 = headA;
        ListNode* cur_node_2 = headB;
        //cal diff of length
        while(cur_node_1 != nullptr && cur_node_2 != nullptr){
            cur_node_1 = cur_node_1->next;
            cur_node_2 = cur_node_2->next;
        }
        //make two start point with same length
        //will exchange point to the other list
        if(cur_node_1 != nullptr) {
            cur_node_2 = headA;
            while(cur_node_1 != nullptr){
                cur_node_1 = cur_node_1->next;
                cur_node_2 = cur_node_2->next;
            }
            cur_node_1 = headB;
        }
        else if(cur_node_2 != nullptr){
            cur_node_1 = headB;
            while(cur_node_2 != nullptr){
                cur_node_2 = cur_node_2->next;
                cur_node_1 = cur_node_1->next;
            }
            cur_node_2 = headA;
        }
        else{
            cur_node_1 = headB;
            cur_node_2 = headA;
        }
        //because len is same, they will meet each other if has joinpoint
        while(cur_node_1 != cur_node_2){
            cur_node_1 = cur_node_1->next;
            cur_node_2 = cur_node_2->next;
        }
        return cur_node_1;
    }

Log in to reply
 

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