链表 寻找2个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。

思路：由于从某个节点开始2个链表相交，那么之后的节点完全一样

先求出2个连表长度  先使得长的链表  先走差值的长度

然后2个指针并排前进，并判断是否相等，若相等即为第一个公共节点

（需要注意 NULL的情况）

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        
        int len1=getLength(pHead1);
        int len2=getLength(pHead2);
        if(len1==0 || len2==0)
            return NULL;
        if(len1>len2) //那么pHead1先走len1-len2步
        {
            for(int i=0;i<len1-len2;i++)
                pHead1=pHead1->next;
        }
        else{
            for(int i=0;i<len2-len1;i++)
                pHead2=pHead2->next;
        }
        //在2个指针并排前行，直到遇到相等
        while(pHead1!=pHead2 && pHead1 && pHead2)
        {
            pHead1=pHead1->next;
            pHead2=pHead2->next;
        }
        return pHead1;
        
        
        
        
    }
    
    int getLength(ListNode* ptr)
    {
        if(ptr==NULL)
            return 0;
        int count=0;
        while(ptr->next!=NULL)
        {
            ptr=ptr->next;
            count++;
        }
        return count;  
        
    }
};

最后

以上就是悦耳薯片为你收集整理的链表 寻找2个链表的第一个公共节点的全部内容，希望文章能够帮你解决链表 寻找2个链表的第一个公共节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。