2.求两个链表的交点

已知链表A的头结点指针headA，链表B的头结点指针headB,两个链表相交，求两链表交点对应的节点。

示意图

注意：

1. 如果两个链表没有交点，则返回NULL；
2. 在求交点的过程中，不可以破坏链表的结构或者修改链表的数据域；
3. 可以确保传入的链表A和链表B没有任何环；
4. 实现算法尽可能使时间复杂度为O(n)，空间复杂度为O(1).

解题思路：

方法一：使用set求交集(时间复杂度为O(nlogn)，空间复杂度为O(n))

1. 遍历链表A，将A中节点对应的指针（地址）插入set中；
2. 遍历链表B，将B中节点对应的指针（地址）在set中查找，发现在set中的第一个节点地址，即为两个链表的交点。
   

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
{
    set<ListNode*> node_set;            // 设置查找集合node_set
    while(headA)
    {
        node_set.insert(headA);        // 将链表A的每个节点的地址插入到node_set中
        headA = headA->next;            // 遍历链表A
    }
    while(headB)
    {
        if ( node_set.find(headB) != node_set.end())    // 当在headB中找到第一个出现在node_set中的节点时
        {
            return headB;
        }
        headB = headB->next;            // 遍历链表B
    }
    return NULL;
}

方法二：时间复杂度为O(n)，空间复杂度为O(1)

int getListLength(ListNode* head)
{
    int len = 0;
    while(head)
    {
        len++;
        head = head->next;
    }
    return len;
}

ListNode* forwardLongList(ListNode* head, int long_len, int short_len)
{
    int delta = long_len - short_len;
    while( head && delta)
    {
        head = head->next;
        delta--;
    }
    return head;
}

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
{
    int list_A_len = getListLength(headA);  // 求链表A的长度
    int list_B_len = getListLength(headB);  // 求链表B的长度
    if (list_A_len > list_B_len)            // 移动较长的链表
    {
        headA = forwardLongList(headA, list_A_len, list_B_len);
    }
    else
    {
        headB = forwardLongList(headB, list_B_len, list_A_len);
    }
    while( headA && headB )
    {
        if ( headA == headB )           // 如果headA == headB,则找到第一个相等的节点
        {
            return headA;
        }
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

完整代码：

方法一c++代码
方法二c++代码