79ms runtime C++ program


  • 0
    A
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            ListNode * pointA = headA;
            ListNode * pointB = headB;
            // measure the length of each list;
            int lenA = 0, lenB = 0;
            while (pointA != NULL) {
                lenA++;
                pointA = pointA -> next;
            }
            while (pointB != NULL) {
                lenB++;
                pointB = pointB -> next;
            }
            // refresh pointA and pointB;
            pointA = headA;
            pointB = headB;
            // if the lengths are different, "cut" the longer one;
            if (lenA > lenB) {
                // cut A
                int n = lenA - lenB;
                while(n) {
                    pointA = pointA -> next;
                    n--;
                }
            }
            if (lenA < lenB) {
                // cut B
                int n = lenB - lenA;
                while(n) {
                    pointB = pointB -> next;
                    n--;
                }
            }
            // if the lengths are the same, two pointers starts from each list's head and compare, finding the intersection;
            while (pointA != NULL && pointB != NULL) {
                if (pointA -> val == pointB -> val && pointA -> next == pointB -> next) {
                        return pointA;
                }
                pointA = pointA -> next;
                pointB = pointB -> next;
            }
            // if searched the whole list while no intersections are found, return NULL
            return NULL;
        }
    };

Log in to reply
 

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