[数据结构与算法]剑指 Offer 52. 两个链表的第一个公共节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

    
        struct ListNode* tailA = headA;
        struct ListNode* tailB = headB;
        int a=0,b=0; //记录两个链表的长度
    if( (tailA==NULL)||(tailB==NULL))
    {
        return NULL;
    }
        while(tailA){ //分别遍历两个链表，记录长度
            tailA=tailA->next;
            a++;
        }
         while(tailB){
            tailB=tailB->next;
            b++;
        }

    if(tailB != tailA){ //两个尾指针不一致，必然不相交
         return NULL;
    }

 //相交求交点
        tailA = headA; //链表指针归位
        tailB = headB;


        int c=0; //c等于两链表长度差
        if (a<b){
          c=b-a;
          //tailB+=c;//链表对齐
          for(int i=0;i<c;i++){
              tailB=tailB->next;
          }
        }
        else{
          c=a-b;
          //tailA+=c;//链表对齐
          for(int i=0;i<c;i++){
              tailA=tailA->next;
          }
        }

        while(tailA!=tailB)
        {
            if(tailA)
                tailA=tailA->next;
            if(tailB)
                tailB=tailB->next;
        }
        return tailA;
           
 
}