剑指offer35-两个链表的第一个公共节点

输入两个链表,找出它们的第一个公共结点。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)

思路:快慢指针,对链表来说,自公共节点后不会分叉;分别计算两个链表长度s1,s2;快指针指向长链表,先走(s2-s1)步;慢指针指向短链表起始位置,接下来两个指针同步向前,当指针指向的值相等时,是第一个公共节点。

    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        //自公共节点后,链表节点相同
        ListNode*p3;
        if(pHead1==NULL||pHead2==NULL) return p3;
        ListNode*p1,*p2;
        p1=pHead1;
        p2=pHead2;
        int s1=0,s2=0;
        while(p1!=NULL)
        {   s1++;
            p1=p1->next;
        }
        while(p2!=NULL)
        {
            s2++;
            p2=p2->next;
        }

            int l=abs(s2-s1);
            p2=pHead2;
            p1=pHead1;
            if(s2>s1)
            {
                while(l--)
                {
                    p2=p2->next;
                }
                
            }
            if(s1>s2)
            {
                while(l--)
                {
                    p1=p1->next;
                }
                
            }
            while(p1&&p2)
            {
                if(p1->val==p2->val)
                {
                    p3=p2;
                    //p3=p2,通过所有测试用例
                    //p3=p1,只能通过50%的测试用例
                    return p3;
                }
                p1=p1->next;
                p2=p2->next;
            }
            return p3;
        
    }

原文地址:https://www.cnblogs.com/trouble-easy/p/12976812.html