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

CodePudding user response：

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