面试题 02.07. 链表相交

Problem: 面试题 02.07. 链表相交

思路

相交节点后的链表是相同的,我们得到两个链表的长度差,开始同时从长度差后的节点同时遍历

错误

 if(aLen < bLen)这里一开始写反了

复杂度

• 时间复杂度:

$O(n+m)$

• 空间复杂度:

$O(1)$

Code

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //遍历一次找出相差多少个节点
        ListNode *a = headA,*b = headB;
        while(a!=nullptr&&b!=nullptr){
            a = a->next;
            b = b->next;
        }
        //计算相差多少个节点
        int diff = 0;
        ListNode *longList,*shortList;
        if(a==nullptr) {
            longList = headB;
            shortList = headA;
        }else {
            swap(a,b);
            longList = headA;
            shortList = headB;
        }
        while(b!=nullptr) {
            b = b->next;
            diff++;
        }
        //让longList先走diff
        while(diff--) longList = longList->next;
        //一起走
        while(longList != nullptr && shortList != nullptr && longList != shortList) {
            longList = longList->next;
            shortList = shortList->next;
        }
        return longList;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a = headA;
        ListNode* b = headB;

        int aLen = 0;
        int bLen = 0;

        while(a != nullptr) {
            aLen++;
            a = a->next;
        }

        while(b != nullptr) {
            bLen++;
            b = b->next;
        }

        a = headA;
        b = headB;

        if(aLen < bLen) {
            swap(aLen,bLen);
            swap(a,b);
        }

        int def = aLen - bLen;
        while(def--) {
            a = a->next;
        }

        while(a != nullptr && a != b) {
            a = a->next;
            b = b->next;
        }

        return a;
    }
};