LeetCode―Intersection of Two Linked Lists 找两个链表的相交位置，让长的链表先走一段 - c++编程基础

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ?
                     c1 → c2 → c3
                   ?            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.

Your code should preferably run in O(n) time and use only O(1) memory. 只能够是O（n）的时间复杂度，这里的做法是首先遍历两个链表知道长度，然后让长的链表先走一段，然后再进行两两比较，时间复杂度O（lengthA+lengthB+maxLength）就是O（n）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL)
        {
            return NULL;
        }
        int lengthA = 1;
        int lengthB = 1;
        ListNode *Afirst = headA;
        ListNode *Bfirst = headB;
        while(Afirst->next)
        {
            lengthA++;
            Afirst = Afirst->next;
        }
        while(Bfirst->next)
        {
            lengthB++;
            Bfirst = Bfirst->next;
        }
        if(Afirst != Bfirst)
        {
            return NULL;
        }
        int length = lengthA;//<随便初始化一个
        if(lengthA > lengthB)
        {
            int diff = lengthA-lengthB;
            length = lengthB;
            while(diff--)
            {
                headA = headA->next;
            }
        }
        if(lengthA < lengthB)
        {
            length = lengthA;
            int diff = lengthB-lengthA;
            while(diff--)
            {
                headB = headB->next;
            }
        }
        while(length--)
        {
            if(headA == headB)
            {
                return headA;
            }
            headA = headA->next;
            headB = headB->next;
        }
        return NULL;
        
    }
};