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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
最开始看到题目能够想到最直接的方法对应的复杂度是n的平方，即两层循环比较指向两个链表的指针是否相同。题目中要求时间复杂度为O(n)，到底应该如何解决呢？
参考如下思路：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *p1 = headA;
    struct ListNode *p2 = headB;
        
    if (NULL == p1 || NULL == p2) 
        return NULL;

    while (p1 != NULL && p2 != NULL && p1 != p2) 
    {
        p1 = p1->next;
        p2 = p2->next;
        
        if(p1 == p2)
            return p1;
        
        if(NULL == p1)
            p1 = headB;
        
        if(NULL == p2)
            p2 = headA;
    }
    
    return p1;
}

算法分析：
如果存在相同部分，假设相同部分为intersection.
ListA = A + intersection
ListB = B + intersection
ListA+ListB = A + intersection + B+ (will meet here)intersection
ListB + ListA = B + intersection + A +(will meet here)intersection
由于A + intersection + B 与B + intersection + A长度相等，当p1==p2即指向了相同部分开始的地方。
如果没有交集，那么ListAListB 与LIstBListA遍历到最后一个元素然后分别next,则 p1与p2相等均为NULL，所以retrun p1(NULL).
今天看到leetcode群里有人讨论这道题，思考10分钟，想到的方法都是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) {
        ListNode *pa = headA,*pb = headB;
        while(pa != pb)
        {
            pa = (pa == NULL)? headB:pa->next;
            pb = (pb == NULL)? headA:pb->next;
        }
        
        return pa;
    }
};

比较中规中矩的解法是使用hash表，详细的代码如下:

/**
 * 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) {
        unordered_set<ListNode *> hash;
        ListNode *pa = headA,*pb = headB;
        while(pa)
        {
            hash.insert(pa);
            pa = pa->next;
        }
        
        while(pb)
        {
            if(hash.count(pb))
                return pb;
            pb = pb->next;
        }
        
        return nullptr;
    }
};