【剑指Offer 52】两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。
示例1

示例2

在节点 2 处相交。

示例3

没有相遇则返回 null
注意：

• 如果两个链表没有交点，返回 null .
• 在返回结果后，两个链表仍须保持原有的结构.
• 可假定整个链表结构中没有循环
• 程序尽量满足 O(n) 的时间复杂度，且仅用 O(1) 的内存

此题使用 双指针 法，使用两个指针 node1 和 node2 从两个链表头节点处依次遍历两个链表，当 node1 到达 链表1 尾节点则返回到 链表2 头节点处重新遍历，当 node2 到达 链表2 尾节点处则回到 链表1 头节点处重新遍历，直至两个指针相遇则是公共节点。

假设链表1的长度是 m+p ，链表2的长度是 n+p 其中 p 是公共长度，那么如果让 node1 走完自己再走别人的路那么总长度是 m+n+p 同理对 node2 也一样，最终两个指针都是走了 m+n+p 的长度，那么就一定会在第一个公共节点处相遇。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *node1 = headA;
    struct ListNode *node2 = headB;
    while (node1 != node2) {
        node1 = node1 != NULL? node1->next:headB;
        node2 = node2 != NULL? node2->next:headA;
    }
    return node1;
}