【题解】两个链表的公共节点

假设用数字相同代表公共节点，设链表A为：{1, 2, 3, 6, 7}, 链表B为：{4， 6， 7}。那么该如何求出第一个公共节点6呢。最容易想到的就是如果末尾对齐的话，两个链表从后向前遍历，遇到最后一个相同的为止。但是链表是单向的，要想将末尾对齐的话，就应该扩展两个链表。将A后面追加一个B，B后面追加一个A，这样两个链表长度都是len(A+B),末尾是对齐的了，意思就是第一个共同节点也一定是对齐的，如果存在的话。
A: 1, 2, 3, 6, 7, 4, 6, 7
B: 4, 6, 7, 1, 2, 3, 6, 7
这样做之后，两个链表同时遍历，肯定能够找到第一个相同的节点。（即使两个链表是没有公共节点的，也会在链表末尾截止）。

时间复杂度为。

实际上，没有必要在代码中进行扩展。只需将一个链表的遍历指针在遍历结束的时候移动到另一个链表的开头即可。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode * p1 = pHead1, * p2 = pHead2;
        while(p1 != p2) {
            p1 = p1==NULL ? pHead2 : p1->next;
            p2 = p2==NULL ? pHead1 : p2->next;
        }
        return p1;
    }
};