[数据结构与算法]相交链表!!!

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

先定义curA和curB遍历链表，看看最后一个节点是不是一个，如果是再寻找第一个相交的节点，如果不是直接返回null。

遍历时计算出各自的链表长度，然后长的链表先走两个长度的差，A、B链表再同时走第一个相等的节点就是第一个相交的节点。

代码实现如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *curA = headA;
    struct ListNode *curB = headB;
    int countA = 1;
    int countB = 1;
    while(curA->next)
    {
        curA = curA->next;
        countA++;
    }
    while(curB->next)
    {
        curB = curB->next;
        countB++;
    }
    if(curA != curB)
    {
        return NULL;
    }
    int gap = abs(countA - countB);
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(countA < countB)
    {
        longList = headB;
        shortList = headA;
    }
    while(gap--)
    {
        longList = longList->next;
    }
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}