Programming Interview Question: Find intersection of two Linked Lists

Problem:
Two linked lists A and B are joined on a particular node, called the point of intersection of the linked lists. Find the point of intersection, i.e. the first node after which both lists have same nodes.

Solution 1:
Keeping a node in List A as fixed and iterating over all nodes in List B to check if there is a node in List B same as the fixed node from List A.
Time Complexity: O(n*m)
Space Complexity: O(1)

Solution 2:
Iterate over first list and put the nodes in a hash set.
Iterate over other list and find the first node that is present in the hash set. This node is the intersection of the 2 lists.
Time Complexity: O(n+m)
Space Complexity: O(n)

Code: http://www.ideserve.co.in/learn/find-intersection-of-two-linked-lists

Website: http://www.ideserve.co.in

Facebook: https://www.facebook.com/IDeserve.co.in

Видео Programming Interview Question: Find intersection of two Linked Lists канала IDeserve