My simple c++ solution with explanations and comments. O(n) time, O(1) space

  • 5

    explanation: the Idea is simple. check which list is longer, for instance A is longer than B with steps nodes. Then the longer one walk the the steps. Now they have the same length. then Both of the lists walk at the same pace until they meet:

       ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA, *curB = headB;
        int size_diff =  0;
        bool flag = false; // false for A shorter, true for B shorter
        while (curA && curB) {
            curA = curA->next;
            curB = curB->next;
        flag = curA; // if curA not null,  B shorter, otherwise, A shorter
        ListNode *start = curA ? curA : curB;
        while(start) {
            start = start->next;
        curA = headA;
        curB = headB;
        if (flag) 
        while (size_diff--) curA = curA->next; // A longer, A walk size_diff steps
        else while (size_diff--) curB = curB->next; // B longer, B walk size_diff 
        while (curA && curB)  // now they walk together
            if (curA == curB) return curA;
            curA = curA->next;
            curB = curB->next;
        return nullptr;

Log in to reply

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