两个链表的第一个公共结点

题目描述

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

思路

两个链表如果有公共结点，有如下特点：

• 一旦相遇，再也不分开，也就是只有'Y'形，没有'X'形。
• 两个链表有公共结点，不是其值相等，而是地址相等
• 解法是遍历两个链表计算出其长度，然后使得两个链表的长度一样，再同时遍历两个链表并两两比较地址。

题解

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==NULL||pHead2==NULL)
            return NULL;
        int len1 = GetLength(pHead1);
        int len2 = GetLength(pHead2);
        //谁长谁先走多出来的部分，直到两个长度一样
        if(len1>len2){
            int len = len1-len2;
            while(len>0){
                pHead1 = pHead1->next;
                len--;
            }
        }else if(len1<len2){
            int len = len2-len1;
            while(len>0){
                pHead2 = pHead2->next;
                len--;
            }
        }
        
        while(pHead1!=NULL){
            if(pHead1 == pHead2)
                break;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return pHead1;
    }
    
private:
    int GetLength(ListNode* pHead){
        int len = 0;
        while(pHead!=NULL){
            len++;
            pHead = pHead->next;
        }
        return len;
        
    }
};