intersection-of-two-linked-lists

intersection_of_two_linked_lists.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
private:
    int lengthOf(ListNode *head) {
        int length = 0;
        for (; head; head = head->next) length += 1;
        return length;
    }
    ListNode* advance(ListNode* head, int steps) {
        for (int i = 0; i < steps; ++i) head = head->next;
        return head;
    }
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int a_length = lengthOf(headA);
        int b_length = lengthOf(headB);
        int min_length = min(a_length, b_length);
        headA = advance(headA, a_length - min_length);
        headB = advance(headB, b_length - min_length);
        for (; headA && headB; headA = headA->next, headB = headB->next) {
            if (headA == headB) return headA;
        }
        return nullptr;
    }
};