Intrerview question: determine whether two linked lists are connected or not

user_17161529 0
Viewed 72

The question is: write a boolean function that receives two linked lists, and returns whether the lists are connected (at some point they both point to the same node). I was not allowed to allocate any memmory like maps, only variables. And they wanted it to be in linear time complexity o(n). My approach was to iterate over one linked list and compare each node to all the nodes in the other list but the complexity of that is o(n^2) and was not good enough

linked-list algorithm
1 Answers

There are two points to consider here:

  1. You need to find if the lists are connected or not.
    That is simple. As pointed out by @user3386109, just check if the last nodes are same and return a boolean.

  2. You need to find the point of intersection as well.
    Here, find the length of both lists (let them be a and b, a>b). Traverse a-b nodes in the first list, then start comparing the nodes in both list one by one to find the point of intersection.

Both cases can be completed in O(N) time and O(1) space

user_93507200
Related