Linked list Interview Question
Intersection in a given linked list
Given pointers to the head nodes of linked lists that merge together at some point, find the Node where the two lists merge. It is guaranteed that the two head Nodes will be different, and neither will be NULL.In the diagram below, the two lists converge at Node x:
[List #1] a--->b--->c \ x--->y--->z--->NULL / [List #2] p--->qComplete the int FindMergeNode(Node* headA, Node* headB) method so that it finds and returns the data value of the Node where the two lists merge.
Input Format
The FindMergeNode(Node*,Node*) method has two parameters, and , which are the non-null head Nodes of two separate linked lists that are guaranteed to converge.
Do not read any input from stdin/console.
Output Format
Each Node has a data field containing an integer; return the integer data for the Node where the two lists converge. Do not write any output to stdout/console.
Sample Input
The diagrams below are graphical representations of the lists that input Nodes and are connected to. Recall that this is a method-only challenge; the method only has initial visibility to those Nodes and must explore the rest of the Nodes using some algorithm of your own design.
Test Case 0 1 \ 2--->3--->NULL / 1 Test Case 1 1--->2 \ 3--->Null / 1 Sample Output 2 3 Explanation Test Case 0: As demonstrated in the diagram above, the merge Node's data field contains the integer (so our method should return ). Test Case 1: As demonstrated in the diagram above, the merge Node's data field contains the integer (so our method should return ). int FindMergeNode(Node *headA, Node *headB) { // Complete this function // Do not write the main method. int a=0,b=0; struct Node* temp = headA; while(temp) { a++; temp=temp->next; } temp = headB; while(temp) { b++; temp=temp->next; } if(a>b) { a-=b; while(a) { headA=headA->next; a--; } while(headA==headB) { headA=headA->next; headB=headB->next; } return headA->data; } else { a=b-a; while(a!=0) { headB=headB->next; a--; } while(!(headA == headB)) { headA=headA->next; headB=headB->next; } return headA->data; } return 0; }Note that this approach is not only specific to this type of question you can use this sorting technique in various questions such as if you want to check whether to word are anagrams of one another or not. You can simply sort them and compare them to find out. This approach is also helpful in other questions so i suggest that its better to learn this tricks and keep in mind while attempting the question you may find it useful. You can always search for more coding problems like this to get comfortable to this to approach or you can find new problems where this approach is applicable. So go and search more problems like this and check whether this approach is useful or not and you can tell me about it by commenting and writing about this to me.
Try more and more problems that you find on string and arrays and try to develop an approach the will help you understand problems rather then learning the solution. Once you know how to approach the problem you will able to solve any problem related to strings and array. I wish best of luck to you for your future.
0 comments:
Post a Comment