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

题目

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

思路

 使用两个指针Node1,node2,分别指向两个链表headA,headB的头节点，然后同时分别逐个节点遍历，当node1到达链表headA的末尾时，重新定位到链表headB的头节点，当node2到达链表headB的末尾时，重新定位到链表headA的头节点。

 两个链表长度分别是L1 + C, L2 + C, C是公共部分长度，那么第一个指针走了L1 + C步之后，回到第二个链表的起点走L2步，第二个人走了L1步，当第二个人走的l2+C步之后，回到第一个人走L1步，当两个人走的步数都是L1 + L2 + C之后，就相遇了。

代码

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
    
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
        ListNode *node1 = headA;
        ListNode *node2 = headB;

        while(node1 != node2)
        {
    
            node1 = node1 != NULL ? node1->next : headB;
            node2 = node2 != NULL ? node2->next: headA;
        }

        return node1;
    }
};