C++ implementation runtime beats 99.69% cppsubmissions


  • 0
    D

    simply count the length of A and B
    Make the longer one's pointer move first, until the left of the longer one has the same length with the other
    Then, move the two pointers together to find if they are intersected

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == NULL || headB == NULL) { return NULL; }
    if (headA == headB) { return headA; }
    else if (headA->next == NULL&&headB->next == NULL) { return NULL; }
    if (headA->next == NULL)
    {
    ListNode
    nodeB = headB;
    while (nodeB != NULL)
    {
    //cout << headA << " " << headA->val<<endl;
    //cout << nodeB << " " << nodeB->val << endl << endl;
    if (headA == nodeB)return headA;
    nodeB = nodeB->next;
    }
    return NULL;
    }
    if (headB->next == NULL)
    {
    ListNode
    nodeA = headA;
    while (nodeA != NULL)
    {
    //cout << headB << " " << headB->val << endl;
    //cout << nodeA << " " << nodeA->val << endl << endl;
    if (nodeA == headB)return headB;
    nodeA = nodeA->next;
    }
    return NULL;
    }
    int Alen = 1;
    int Blen = 1;
    ListNode
    node = headA;
    while (node->next != NULL)
    {
    Alen++;
    node = node->next;
    }
    node = headB;
    while (node->next != NULL)
    {
    Blen++;
    node = node->next;
    }
    int diff = Blen - Alen;
    ListNode* nodeA = headA;
    ListNode* nodeB = headB;
    //Blen>Alen
    if (diff>0)
    {
    for (int i = 0; i < diff; i++)
    {
    nodeB = nodeB->next;
    }
    if (nodeA == nodeB)return nodeA;
    while (nodeA->next != NULL&&nodeB->next != NULL)
    {
    nodeA = nodeA->next;
    nodeB = nodeB->next;
    if (nodeA == nodeB)return nodeA;
    }
    }
    else
    {
    for (int i = 0; i < (-diff); i++)
    {
    nodeA = nodeA->next;
    }
    if (nodeA == nodeB)return nodeA;
    while (nodeA->next != NULL&&nodeB->next != NULL)
    {
    nodeA = nodeA->next;
    nodeB = nodeB->next;
    if (nodeA == nodeB)return nodeA;
    }
    }
    return NULL;
    }


Log in to reply
 

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