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

题目：

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pH*=ead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

解题思路：

因为我们要找的是两个链表的第一个公共结点，所以我们首先想到的可能是遍历链表，找到第一个公共结点，但是这种方法有两个循环，时间复杂度会偏高，我们希望能找出线性时间复杂度的方法来解决问题。
如果想要用线性时间复杂度的方法来解决问题，有一种理想的状态：两个链表的长度相同。

对于这样的情况下，我们可以分别从链表a和链表b的头结点开始遍历，直到第一个公共结点出现时，返回该结点，否则则没有公共结点，这时指针正好走到链表的尾部，指针指向nullptr，返回nullptr。
但是，题目的输入链表长度并不相同，所以我们想办法把它们构造成理想状态，假设链表a长度为m，链表b长度为n，m！=n，但是m+n=n+m，所以我们可以把链表互相链接起来。

不论是链接在前面还是后面，由于长度是相同的，那么从链表的尾部来看，都会是两个原本列表的尾部，

• 如果有公共结点，那么从尾部开始就时一一对应的，我们只需要从前往后遍历，找到第一个公共结点即可。
• 如果没有公共结点，那么从尾部开始就没有一一对应的结点，从前往后遍历直到最后，返回nullptr即可。

解题代码：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* p1=pHead1,*p2=pHead2;
        //直到最后找到公共结点或者是到达合成链表的尾部
        while(p1!=p2){
            p1=p1?p1->next:pHead2;//如果p1遍历到尾部，则从链表2开始接着遍历
            p2=p2?p2->next:pHead1;//如果p2遍历到尾部，则从链表1开始接着遍历
        }
        return p1;
    }
};