CareerCup

In the case of sorted linked list
1.Make two pointers pointing to each head ptr1,ptr2.
2.if(ptr1->data==ptr2->data) two pointers are pointing same node return the current node
3.else if ptr1->data>ptr2->data then increment ptr1 to next node
4.else increment ptr2 to next node
5.goto second step

if linked list is not sorted one..
1.make two pointers pointing to each head.
2.find number of nodes in each pointers.
3.find the difference of each count
4.move the longest list pointer for above difference from the head
5.the move the each pointer,return the meeting point.

<pre lang="" line="1" title="CodeMonkey27600" class="run-this">#include<stdio.h>
#include<stdlib.h>

/* Link list node */
struct node
{
int data;
struct node* next;
};

/* Function to get the counts of node in a linked list */
int getCount(struct node* head);

/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct node* head1, struct node* head2);

/* function to get the intersection point of two linked
lists head1 and head2 */
int getIntesectionNode(struct node* head1, struct node* head2)
{
int c1 = getCount(head1);
int c2 = getCount(head2);
int d;

if(c1 > c2)
{
d = c1 - c2;
return _getIntesectionNode(d, head1, head2);
}
else
{
d = c2 - c1;
return _getIntesectionNode(d, head2, head1);
}
}

/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct node* head1, struct node* head2)
{
int i;
struct node* current1 = head1;
struct node* current2 = head2;

for(i = 0; i < d; i++)
{
if(current1 == NULL)
{ return -1; }
current1 = current1->next;
}

while(current1 != NULL && current2 != NULL)
{
if(current1 == current2)
return current1->data;
current1= current1->next;
current2= current2->next;
}

return -1;
}

/* Takes head pointer of the linked list and
returns the count of nodes in the list */
int getCount(struct node* head)
{
struct node* current = head;
int count = 0;

while (current != NULL)
{
count++;
current = current->next;
}

return count;
}

/* IGNORE THE BELOW LINES OF CODE. THESE LINES
ARE JUST TO QUICKLY TEST THE ABOVE FUNCTION */
int main()
{
/*
Create two linked lists

1st 3->6->9->15->30
2nd 10->15->30

15 is the intersection point
*/

struct node* newNode;
struct node* head1 =
(struct node*) malloc(sizeof(struct node));
head1->data = 10;

struct node* head2 =
(struct node*) malloc(sizeof(struct node));
head2->data = 3;

newNode = (struct node*) malloc (sizeof(struct node));
newNode->data = 6;
head2->next = newNode;

newNode = (struct node*) malloc (sizeof(struct node));
newNode->data = 9;
head2->next->next = newNode;

newNode = (struct node*) malloc (sizeof(struct node));
newNode->data = 15;
head1->next = newNode;
head2->next->next->next = newNode;

newNode = (struct node*) malloc (sizeof(struct node));
newNode->data = 30;
head1->next->next= newNode;

head1->next->next->next = NULL;

printf("\n The node of intersection is %d \n",
getIntesectionNode(head1, head2));

getchar();
}</pre><pre title="CodeMonkey27600" input="yes">
</pre>

i dont think u fully understand the question. it s not asking for intersection. it s asking for an intersection where the rest of the elements are same after the intersection. in other words. the last intersection.

so the right answer is to have two pointers iterating from the end of the array until there s an intersection and that s the node where it forms a Y shape.

I think ur inked list forms x shape ... They asked me y shaped linked list ...so the fisrt ocurring node whr the list intersects... Wht data structur wud u use ...?
etc etc btw .... They also asked me what are hashtables... Binary tree search time...definition what a test plan? How wud u assure quality control ? I didnt say much for this but it was asked in 1st phone interview...what made me wonder if i applied for qa or sdetlaters icame to knw they r the same in amazon ...:| they asked me qa ques in 1st phone interview black box white box etc etc and some application based q i dont remeber that exactly.

lol how in the world can a linked list be X shaped? how can a single intersection node point to 2 diff. 'next's?

We denotes the three segments of the Y-shapped linked list l1, l2 and l3, and let the l3 be the list contains the intersecting node. By traversing throught the two linked lists l1-l3 and l2-l3, we could get len(l1 + l3) and len(l2 + l3). Then by reversing l1-l3 (l2-l3 is also ok) and going throught l2-intersectingNode-l1 we could get len(l2 + l1) + 1. The last step will be the work of sloving these equations.
This algorithm has a linear time complexity.

Ok I don't think any solutions so far is right. Consider the case where the lengths of two lists are equal. In this case one can iterate both head pointers till they point to the same element. Now in the general case where list lengths may not be equal, find both lengths and move the head of the longer list to number of nodes which is equal to the difference of the lengths of two lists. From now on both head lengths are same so you can simply iterate and find the common element. This also works for the case where one list starts in the middle of another list !

Well, there are several approaches to solve this problem.

Note that i am only discussing the approaches[corner cases may need to be handled separately] starting from brute force to the best one.
Considering N: number of nodes in first linked list
M: number of nodes in second linked list

Approach 1:
Compare each node of first linked list with every other node of second list. Stop when you find a matching node, this is the merging point.

while(head1)
{
cur2=head2;
while(cur2)
{
    if(cur2==head1)
        return cur2;
    cur2=cur2->next;
}
head1=head1->next;
}

Time Complexity: O(N*M)
Space Complexity: O(1)

Approach 2:
Maintain two stacks. Push all the nodes of he first linked list to first stack. Repeat he same for second linked list.
Start popping nodes from both the stacks until both popped nodes do not match. The last matching node is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 3:
Make use of hash table. Insert all the nodes of the first linked list into hash.
Search for the first matching node of he second list in the hash.
This is the merging point.
Time Complexity: O(N+M)
Space Complexity: O(N)
Note that the space complexity may vary depending upon the hash function used[talking about C where you are supposed to implement your own hash function].

Approach 4:
Insert all the nodes of first linked list[by nodes, i mean addresses] into an array.
Sort the array with some stable sorting algorithm in O(N logN) time[Merge sort would be better].
Now search for the first matching node from the second linked list.
Time Complexity: O(N logN)
Space Complexity: O(N)
Note that this approach may be better than Approach 3 [in terms of space]as it doesn't use a hash.

Approach 5:
1. Take an array of size M+N.
2. Insert each node from the first linked list, followed by inserting each node from the second linked list.
3. Search for the first repeating element[can be found in one scan in O(M+N) time].
Time Complexity: O(N+M)
Space Complexity: O(N+M)

Approach 6: [A better approach] 1. Modify the first linked list & make it circular.
2. Now starting from the head of the second linked list, find the start of the loop using Floyd- Warshall cycle detection algorithm.
3. Remove the loop[can be easily removed as we know the last node].
Time Complexity: O(N+M)
Space Complexity: O(1)

Approach 7: [Probably the best one]
1. Count the number of nodes in first linked list[say c1].
2. Count the number of nodes in second linked list[say c2].
3. Find the difference[Lets say c1>c2] diff=c1-c2.
4. Take two pointers p1 & p2, p1 pointing to the head of the first linked list & p2 pointing to the head of the second linked list.
5. Move p1 diff times.
6. Move both p1 & p2 each node at a time until both point to the same node.
7. p1 or p2 indicates the merging point.
Time Complexity: O(N+M)
Space Complexity: O(1)