《手撕链表题系列-8》相交链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //创建寻址指针
    struct ListNode*cur1=headA,*cur2=headB;
    //计算各链表的长度
    int len1=1,len2=1,gas;
    while(cur1->next)
    {
        len1++;
        cur1=cur1->next;
    }
    while(cur2->next)
    {
        len2++;
        cur2=cur2->next;
    }
    //各链表尾节点不相等则两链表不相交
    if(cur1!=cur2)
    return false;
    //接下来则是必定有相交节点的情况
    //判断长短并记录
    struct ListNode*geater,*less;
    if(len1>=len2)
    {
        geater=headA;
        less=headB;
        gas=len1-len2;
    }
    else
    {
        geater=headB;
        less=headA;
        gas=len2-len1;
    }
    //长链表先走差距长度
    while(gas--)
    {
        geater=geater->next;
    }
    //一同走，相等时则找到相交节点
    while(geater!=less)
    {
        geater=geater->next;
        less=less->next;
    }
    return geater;
}