Let's say there are two lists of varying lengths that merge at a certa

1.	Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?
Answer» You begin with List 1 and assume that the NULL at the end is a pointer to the start of List 2, giving the illusion of a cyclic list. After that, the algorithm will inform you how far down List 1 the merging is. Make an iterator pointer that runs forward until it reaches the end of the list, then jumps to the start of the opposite list, and so on. Make two of them, each pointing to two different heads. Each time you advance the pointers by one, they will eventually meet in the intersection point (IP). After one or two passes, this will occur. Count the number of nodes traversed from head1-> tail1-> head2 -> intersection point and head2-> tail2-> head1 -> intersection point to have a better understanding. Both will be equal (Draw diff types of linked lists to verify this). The reason for this is that both pointers must traverse identical distances (head1->IP + head2->IP) before returning to IP. As a result, by the time it reaches IP, both pointers will be equal, and we will have ARRIVED at the merging point. Node* getIP(Node* head1, Node* head2){ // two pointers ptr1 and ptr2 // at the heads of the two lists Node* P1 = head1; Node* p2 = head2; if (p1 == NULL \|\| p2 == NULL) return NULL; // the two lists are to be traversed until we reach the IP while (p1 != p2) { p1 = p1->next; p2 = p2->next; // When p1 reaches the end of the list, it is // redirected to head2. if (p1 == NULL) p1 = head2; // When p2 reaches the end of the list, it is // redirected to head1. if (p2 == NULL) p2 = head1; // If at any node p1 meets p2, we have got our IP. if (p1 == p2) return p2; } return p2;} OR Make a circular linked list by traversing the FIRST linked list (counting the ELEMENTS). (Keep track of the last node so we can break the circle later.) Reframe the issue as locating the loop in the second linked list. We already KNOW the length of the loop which is equal to the length of the first linked list. We have to traverse those many numbers of nodes in the second list first, and then another pointer should be started from the beginning of the second list. We have to continue traversing until they meet, and that is the required intersection point. The circle should be removed from the linked list. Both the approaches have O(n+m) time and O(1) space complexity.

Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?

Answer»

You begin with List 1 and assume that the NULL at the end is a pointer to the start of List 2, giving the illusion of a cyclic list. After that, the algorithm will inform you how far down List 1 the merging is.

Make an iterator pointer that runs forward until it reaches the end of the list, then jumps to the start of the opposite list, and so on.
Make two of them, each pointing to two different heads.
Each time you advance the pointers by one, they will eventually meet in the intersection point (IP). After one or two passes, this will occur.

Count the number of nodes traversed from head1-> tail1-> head2 -> intersection point and head2-> tail2-> head1 -> intersection point to have a better understanding. Both will be equal (Draw diff types of linked lists to verify this). The reason for this is that both pointers must traverse identical distances (head1->IP + head2->IP) before returning to IP. As a result, by the time it reaches IP, both pointers will be equal, and we will have ARRIVED at the merging point.

Node* getIP(Node* head1, Node* head2){ // two pointers ptr1 and ptr2 // at the heads of the two lists Node* P1 = head1; Node* p2 = head2; if (p1 == NULL || p2 == NULL) return NULL; // the two lists are to be traversed until we reach the IP while (p1 != p2) { p1 = p1->next; p2 = p2->next; // When p1 reaches the end of the list, it is // redirected to head2. if (p1 == NULL) p1 = head2; // When p2 reaches the end of the list, it is // redirected to head1. if (p2 == NULL) p2 = head1; // If at any node p1 meets p2, we have got our IP. if (p1 == p2) return p2; } return p2;}

Make a circular linked list by traversing the FIRST linked list (counting the ELEMENTS). (Keep track of the last node so we can break the circle later.)
Reframe the issue as locating the loop in the second linked list.
We already KNOW the length of the loop which is equal to the length of the first linked list. We have to traverse those many numbers of nodes in the second list first, and then another pointer should be started from the beginning of the second list. We have to continue traversing until they meet, and that is the required intersection point.
The circle should be removed from the linked list.

Both the approaches have O(n+m) time and O(1) space complexity.

Let's say there are two lists of varying lengths that merge at a certain point; how do we know where the merging point is?

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment