[sword finger offer] 52 The first common node of two linked lists

The finger of the sword Offer 52. The first common node of two linked lists

subject

Enter two linked lists , Find their first common node .

Ideas

  Using two Pointers Node1,node2, Point to two linked lists respectively headA,headB The head node of , Then traverse node by node at the same time , When node1 Reach the linked list headA At the end of , Relocate to the linked list headB The head node of , When node2 Reach the linked list headB At the end of , Relocate to the linked list headA The head node of .

  The lengths of the two linked lists are L1 + C, L2 + C, C Is the length of the common part , So the first pointer goes L1 + C After step , Go back to the starting point of the second linked list L2 Step , The second man left L1 Step , When the second person left l2+C After step , Go back to the first person L1 Step , When two people take the same number of steps L1 + L2 + C after , Just met .

Code

/** * 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;
    }
};