【题目】

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.

【分析】

如果两个没有环的链表相交于某个节点，那么在这个节点之后的所有节点都是两个链表所共有的。

（1）遍历链表A，记录其长度len1，遍历链表B，记录其长度len2。

（2）按尾部对齐，如果两个链表的长度不相同，让长度更长的那个链表从头节点先遍历abs(len1-en2),这样两个链表指针指向对齐的位置。

（3）然后两个链表齐头并进，当它们相等时，就是交集的节点。

时间复杂度O(n+m)，空间复杂度O(1)

【代码】

    /*------------------------------------
    *   日期：2015-01-31
    *   作者：SJF0115
    *   题目: 160.Intersection of Two Linked Lists
    *   网址：https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    struct ListNode{
        int val;
        ListNode *next;
        ListNode(int x):val(x),next(NULL){}
    };

    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            int len1 = 0,len2 = 0;
            ListNode *pA,*pB;
            pA = headA;
            // 统计第一个链表节点数
            while(pA){
                ++len1;
                pA = pA->next;
            }//while
            pB = headB;
            // 统计第一个链表节点数
            while(pB){
                ++len2;
                pB = pB->next;
            }//while
            pA = headA;
            pB = headB;
            // 长度相等且只一个节点一样
            if(len1 == len2 && pA == pB){
                return pA;
            }//if
            // pA指向长链表 pB指向短链表
            if(len1 < len2){
                pA = headB;
                pB = headA;
            }//if
            // pA,Pb指向相同大小位置的节点上
            int as = abs(len1- len2);
            for(int i = 0;i < as;++i){
                pA = pA->next;
            }//while
            // 比较是不是相交点
            while(pA){
                if(pA == pB){
                    return pA;
                }//if
                pA = pA->next;
                pB = pB->next;
            }//while
            return nullptr;
        }
    };

[LeetCode]160.Intersection of Two Linked Lists