#链表 #链表相交

intersection-of-two-linked-lists-lcci.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    ListNode* GetNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;

        // [head, cur node] 区间有 n 个node
        ListNode* cur = dummy; 
        for (int i = 0; i < n; ++i) {
            cur = cur->next;
        }

        // [candidate, cur] 区间有 n+1 个node
        ListNode* candidate = dummy;
        while (cur->next != NULL) {
            cur = cur->next;
            candidate = candidate->next;
        }

        // [ret node, last node] 区间有 n 个node
        return candidate->next;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL)
            return NULL;

        int m = 0, n = 0;
        ListNode* curA = headA;
        while (curA != NULL) {
            curA = curA->next;
            m++;
        }
        ListNode* curB = headB;
        while (curB != NULL) {
            curB = curB->next;
            n++;
        }

        bool is_A_shorter = m < n ? true : false;
        int len_min = is_A_shorter ? m : n;
        int len_max = is_A_shorter ? n : m;
        ListNode* tmpShort  = is_A_shorter ? headA : headB;
        ListNode* headLong  = is_A_shorter ? headB : headA;
        ListNode* tmpLong = GetNthFromEnd(headLong, len_min);

        while(tmpShort != NULL) {
            if (tmpLong == tmpShort) 
                return tmpShort;
            tmpShort = tmpShort->next;
            tmpLong = tmpLong->next;
        }
        return NULL;
    }
};