52剑指OFFER之两个链表的第一个公共节点

参考资料：

[1]剑指OFFER课本第3种解法

关键词：

先得到链表的长度，再归位指针。一个链表先走k步，然后两个一起走

注意：

统计完长度，记得把指针弄回原来的地方！！！！还有，两个链表可以没有公共节点。

自己的解法：

改进版：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        
        if (pHead1 == nullptr || pHead2 == nullptr)
            return nullptr;

        int nLen1, nLen2;
        nLen1 = nLen2 = 0;

        ListNode* pNode1 = pHead1;
        ListNode* pNode2 = pHead2;

        //步骤1:先统计链表1和链表2的长度
        while (pNode1 != nullptr)
        {
            nLen1++;
            pNode1 = pNode1->next;
        }

        while (pNode2 != nullptr)
        {
            nLen2++;
            pNode2 = pNode2->next;
        }
        int nDiff = abs(nLen1-nLen2);
        //步骤2：两个链表的长度相减，其中一个长的链表先走diff步，然后一起走
        pNode1 = pHead1;
        pNode2 = pHead2;
        if (nLen1 >= nLen2)
        {
            while (nDiff--)
            {
                pNode1 = pNode1->next;
            }
        }
        else
        {
            while (nDiff--)
            {
                pNode2 = pNode2->next;
            }
        }
        //两个指针一起走，即使两个链表没有公共节点，也是可以的
        while (pNode1 != pNode2)
        {
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode1;
    }
        
};

初始版：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        
        //思路：
        //步骤1：各自统计两个链表的长度
        //步骤2：得到两个链表的长度差，长的链表先走长度差的大小，然后一起走，如果相等就是第一个公共节点
        
        
        if(pHead1 == nullptr || pHead2 == nullptr)
            return nullptr;
        //步骤1：各自统计两个链表的长度
        ListNode* pNode1 = pHead1;
        ListNode* pNode2 = pHead2;
        
        int len1=0;
        while(pNode1 != nullptr)
        {
            pNode1= pNode1->next;
            len1++;
        }
        int len2 =0;
        while(pNode2 != nullptr)
        {
            pNode2 = pNode2->next;
            len2++;
        }
        //记得归位啊！！！！！！！！！！！！！！！！！！！！
        pNode1 = pHead1;
        pNode2 = pHead2;
        //步骤2：得到两个链表的长度差，长的链表先走长度差的大小，然后一起走，如果相等就是第一个公共节点
        int diff = 0;
        if(len1>=len2)
        {
            diff = len1-len2;
            for(int i =1;i<=diff;i++)
            {
                pNode1 = pNode1->next;
            }
        }
        else
        {
            diff = len2-len1;
            for(int i =1;i<=diff;i++)
            {
                pNode2 = pNode2->next;
            }
        }
        
        while(pNode1 != pNode2)
        {
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode1;
    }
        
};

标准答案：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
       
      //步骤1：找到链表的长度
        ListNode* p1=pHead1;
        ListNode* p2=pHead2;
        int length1= 0,length2 = 0;
        while(p1 != NULL)
        {
            p1 = p1->next;
            length1++;
        }
        while(p2 != NULL)
        {
            p2 = p2->next;
            length2++;
        }
        //步骤2：找到两个长度的差
        int differ=0;
        if(length1>length2)
        {
            differ= length1-length2;
            p1 = pHead1;//长一点的
            p2 = pHead2;
        }
        else
        {
            differ = length2-length1;
            p1 = pHead2;//长一点的
            p2 = pHead1;
        }
        //步骤3：长的先前进几步
        for(int i=0;i<differ;i++)
        {
            p1 = p1->next;
        }
        
        //步骤4：找到公共节点
        while(p1 != NULL)
        {
            if(p1 ==p2)
                return p1;
            p1= p1->next;
            p2= p2->next;
        }
        return p1;
        
    }
        
};