leetcode 160 两链表交点

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

这个问题的核心是2个链表长度不同。两个做法，一个是计算出长度，然后长的先走多出来的长度，不过我的代码写的不好，如果不创建子函数总是超时；还有一种方法就是链表走到头了之后去走别人的链表，设A的长度为lA，B的长度为lB，且lA<lB，那么A走完后还要走lB，此时B还剩lB-lA，然后要走A的话要走lA，所以B的路程=lB-lA+lA=lB。这样就相当于走了同样的路程。

那么代码也很好写了，如下：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr)  //有空链表直接return
            return nullptr;
        ListNode *A = headA, *B = headB;
        while(A && B){
            if(A == B)
                return A;
            A = A->next;
            B = B->next;
            if(A == B)
                return A;
            if(A == nullptr)
                A = headB;
            if(B == nullptr)
                B = headA;
        }
        return A;
    }
};  //整个算法没啥好解释的了^_^