Tuesday, December 1, 2009

Find common meet point node of two link lists?

Question:

There are two link list, which meet at some node X,find the meet point?

Hints:
-> There may be more then 1 common nodes
-> The length of both the link list might not be same

Constraints:
-> Time & Space complexity to be minimal

Example:

List 1: 1-2-3-4-5-6-7

List 2: a-b-c-6-7

Here "Node 6" is the meet point.

Answer:

-> Take two pointers, each pointing to head of each list
-> Take two counter variables for each list to store the length of list

-> Traverse both the list and increment the count on each node traversal
-> Get the length difference by subtracting the counter with higher value to lower one and put to some difference variable

-> Increment the pointer "difference variable" times whose length is greater

-> Increment both the pointers and compare at each iteration, till any node reaches the tail
-> The point at which both the pointers get same value is the common node meet point

Complexity:

Time: O(2N) -> O(N) , where N represents longest link list length
Space: O(3) -> O(1)

Example:

List 1: 1-2-3-4-5-6-7

List 2: a-b-c-6-7

Here "Node 6" is the meet point.

Tracing:

Step 1:

-> Let Pointer 1 points to head of List 1 and counter is Length 1
-> Let Pointer 2 points to head of List 2 and counter is Length 2

Step 2:

-> The Length 1 value will be: 7
-> The Length 2 value will be: 5
-> Difference variable value will be: 2

Step 3:

-> List 1 length is bigger, hence Pointer 1 will be incremented two time to point to Node 2

Step 4:

Movement of Pointer 1: 3-4-5-6
Movement of Pointer 2: a-b-c-6

Node 6 is the common meet point.

Answer:

Node 6

No comments:

Post a Comment

Disclaimer:

The above post and all the posts in the blog are derived from facts, information, logical interpretation and logical conclusion of printed and internet materials available to me, perceived and produced by 99 gm brain of mine, which by no means always be accurate, consistent and complete.

All the posts are for personal quick reference only.

If any suggestion, correction, misinterpretation, misconception commented, which will be moderated and deleted if required, to avoid unforeseen issues.

If any trademark / copywrite issue is present, do send in a mail and appropriate tag (logo, name, website link) will be attached to the same.

Additional disclaimer will be attached wherever required in the post.