题目描述

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

For example, the following two linked lists:

题意：给两个链表，找到两个链表第一次相交的位置，如果两个链表不相交返回NULL。

算法1

题解1:很自然的思路，先分别遍历两个链表求的两个链表的长度，让长度较长的链表先走完这个长度差，然后两个链表一起移动第一次相等就是答案。

C++ 代码

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0,lenB = 0;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA != NULL){lenA ++ ; curA = curA->next;}
        while(curB != NULL){lenB ++ ; curB = curB->next;}
        if(lenA == 0 || lenB == 0) return NULL;
                if(lenA > lenB)
        {
            for(int i = 0 ; i < lenA - lenB; i ++)
                headA = headA->next;
        }else
            {
            for(int i = 0 ; i < lenB - lenA; i ++)
                headB = headB->next;
            }
        if(headA == headB) return headA;
            while(headA != NULL)
            {
            headA = headA->next;
            headB = headB->next;
            if(headA == headB)
              return headA;
            }
            return NULL;
    }

算法2

题解2:看了官方题解的提示和借鉴了@yxc的题解。首先两个链表从头开始走，$pA$如果不等于NULL就继续走，如果等于NULL，就$pA = headB$，$pB$如果不等于NULL就继续走，如果等于NULL，就$pB = headA$。他们第一次相交的位置就是答案。

如果二者不相交：那么分走了$lenA+lenB$的距离到达了NULL节点。如果二者相交，第一个节点走$a+c+b$，第二个节点走了$b+c+a$个节点在相交处相遇。

C++ 代码

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        while(curA !=curB)
        {
            if(curA != NULL) curA = curA->next;
            else curA = headB;
            if(curB != NULL) curB = curB->next;
            else curB = headA;
        }
        return curA;
    }