题解 | #两个链表的第一个公共结点#

利用双指针求解：

1、先得到两个链表的长度；

2、如果两个链表的长度不同，则将长度较长的链表先移动，使得两个链表剩余的结点数相同；

3、两个链表再同时移动，如果两个链表有公共结点，移动过程中一定会相遇在第一个公共结点。

时间复杂度：o(n)

空间复杂度：o(1)

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
	  	//特殊情况处理
        if (pHead1 == nullptr || pHead2 == nullptr)
            return nullptr;

        int length1 = 0;
        int length2 = 0;
        ListNode* ptemp1 = pHead1;
        ListNode* ptemp2 = pHead2;
        //得到两个链表的长度
        while (ptemp1) {
            length1++;
            ptemp1 = ptemp1->next;
        }
        while (ptemp2) {
            length2++;
            ptemp2 = ptemp2->next;
        }
        //长度较长的链表先移动，使得两个链表剩余的节点数相同
        if (length1 != length2) {
            if (length1 < length2) {
                for (int i = 0; i < length2 - length1; i++)
                    pHead2 = pHead2->next;             
            } else {
                for (int i = 0; i < length1 - length2; i++)
                    pHead1 = pHead1->next;          
            }
        } 
		while (pHead1 && pHead2) {
			if (pHead1 == pHead2)
                return pHead1;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }

        return nullptr;
    }
};

如下有更便捷的写法

假设A、B两个链表的长度不同，但是，a+b = b+a 因此，可以让 a+b 作为链表A的新长度，b+a作为链表B的新长度。

当A链表移动到尾节点时，下一个节点变成B的头结点；当B链表移动到尾节点时，下一个节点变成A的头结点。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *ta = pHead1, *tb = pHead2;
        while (ta != tb) {
            ta = ta ? ta->next : pHead2;
            tb = tb ? tb->next : pHead1;
        }
	  	//返回公共结点或者返回NULL
        return ta;
    }
};