|
Answer» Let's take an EXAMPLE of the following two linked lists which intersect at node c1. Intersection of Two Linked ListSolution - - Get count of the NODES in the first list, let count be c1.
- Get count of the nodes in the second list, let count be c2.
- Get the difference of counts d = abs(c1 – c2)
- Now traverse the bigger list from the first node till d nodes so that from here ONWARDS both the lists have an equal no of nodes
- Then we can traverse both the lists in parallel till we COME across a common node. (Note that getting a common node is done by comparing the address of the nodes)
// Function to get the intersection point // of the given linked lists int getIntersectionNode(Node* head1, Node* head2) { Node *curr1 = head1, *curr2 = head2; // While both the pointers are not equal while (curr1 != curr2) { // If the first POINTER is null then // set it to point to the head of // the second linked list if (curr1 == NULL) { curr1 = head2; } // Else point it to the next node else { curr1 = curr1->next; } // If the second pointer is null then // set it to point to the head of // the first linked list if (curr2 == NULL) { curr2 = head1; } // Else point it to the next node else { curr2 = curr2->next; } } // Return the intersection node return curr1->data; }
|
