526互联

LeetCode 面试题 02.07. 链表相交

发布时间 2023-03-26 14:06:30作者: 章章_思游容

面试题 02.07. 链表相交 力扣 题目跳转链接

思路参考：代码随想录 跳转链接


错误代码:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode* fast;
        ListNode* slow;
        int sizeA=0,sizeB=0,gap=0;
        while(headA)   //很明显 这里headA又没有改变。 会一直循环下去！！！
        {sizeA++;}

        while(headB)
        {sizeB++;}
        gap=abs(sizeB-sizeA);

        if(sizeA>sizeB)
        { swap(headB,headB);}

        slow=headA;
        fast=headB;
        while(gap--)
        {
            fast=fast->next;
        }

        while(fast)
        {
            if(fast==slow)
            {
                return fast;
            }
            fast=fast->next;
            slow=slow->next;
        }
       return nullptr;
    }
};


错误记录2：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        //假定B 长   A 短
        ListNode* fast=headB;
        ListNode* slow=headA;
        int sizeA=0,sizeB=0,gap=0;
        while(fast)    //fast 对应的是 B  sizeB 233、、、
        {sizeA++;
         fast=fast->next;
        }

        while(slow)
        {sizeB++;
        slow=slow->next;
        }
        gap=abs(sizeB-sizeA);
** //这里是不对的 。   题目要求：注意，函数返回结果后，链表必须 保持其原始结构 。
逻辑： 
        if(sizeA>sizeB)
        { swap(headA,headB);}

        slow=headA;
        fast=headB;

**
        while(gap--)
        {
            fast=fast->next;
        }

        while(fast)
        {
            if(fast==slow)
            {
                return fast;
            }
            fast=fast->next;
            slow=slow->next;
        }
       return nullptr;
    }
};