Sunday, June 2, 2013

[Expedia Interview] Intersection of two link list

Given two link lists intersecting in the following manner


 check whether the two list intersect or not, if it does find the point of intersection.



Approach:
First gotcha in the problem is that such a linked list cannot exist. Since it is a singly linked list hence a node cannot have 2 next pointers.
So the problem reduces to the Y shaped linked list.

Now we observe that the pointer D is common to both the list and to find if the list intersect  or not it is sufficient to find if both the list have a common pointer among their start or end pointers.
Finding the point of intersection is now trivial and left to the reader.

1 comment :

  1. Admiring the time and effort you put into your website and detailed information you provide.
    It's good to come across a blog every once in a while that isn't the same outdated
    rehashed information. Fantastic read! I've bookmarked your site and I'm including your RSS feeds to my Google
    account.

    ReplyDelete