160.相交链表

目录

一、思路分析：

二、源码

一、思路分析：

第一，算出两个链表的长度差K

第二，长的先走K步，然后同时走，相同的节点即为第一个相交节点

但是注意：如果是相交，那么两个链表最后一个节点一定相同，否则就是不相交

二、源码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int lenA,lenB;
    lenA = lenB = 1;
    struct ListNode *curA = headA, *curB = headB;
        //A的长度
        while(curA->next)
        {
            lenA++;
            curA = curA->next;
        }
         //B的长度
        while(curB->next)
        {
            lenB++;
            curB = curB->next;
        }
        if(curA != curB)
        {
            return NULL;
        }
        else
        {
            int k = abs(lenA-lenB);
            //假设A比较长
           struct ListNode *longList = headA, *shortList = headB;
           if(lenB > lenA)
           {
               longList = headB;
               shortList = headA;
           }
           while(k--)
           {
               longList = longList->next;
           }
           while(longList != shortList)
           {
               longList = longList->next;
               shortList = shortList->next;
           }
           return longList;
        }
}