TEKPOOL

Q: You are given two singly linked lists, such that they start from two different nodes (head) and then, a few nodes down the list, they meet at a common node and then share all the nodes henceforth until the tail. The task is to find the first common node.

Sol:

There are a few ways to solve this. The trivial solution would involve storing all the nodes of the smaller list and traverse each node in the bigger list, comparing each node to the already stored nodes. Instead of storing the nodes you can traverse the whole (smaller) list each time. It is clear however, the each of these are inefficient (time and space)

----------------------------------------------------------------------------------------

Here's another way to do this. Much more efficient but requires modifying the original list

Let list L1 have 'a' number of nodes leading to the intersecting node and 'k' number do nodes afterwards;

a+k=len1 --> equation 1

Let list L2 have 'b' number of nodes leading to the intersecting node and 'k' number do nodes afterwards;

b+k=len2 --> equation 2

You can calculate len1 and len2 by traversing the list

subtracting the above 2 equations you get

a-b= len1-len2; --> equation 3

Now reverse List 2 and then traverse from the head of List 1 and count the number of nodes as you go, you will eventually reach the original head of List 2. Let the length you just computed be len 3

a+b = len 3 --> equation 4

You have 2 equations (3 and 4) and 2 unknowns (a and b)

a and b are the lengths of list from the head of each list to the intersecting node.

You can re-reverse List L2 to revert it to the original state

----------------------------------------------------------------------------------------

Sometimes you do not want to alter the start of list. In multithreaded applications, other threads could be reading from the list and Locking leads to performance issues. The following solution will solve the problem without actually altering the list

First, Traverse the 2 lists and find their lengths (L1 and L2). Traversing the longer list starting from its head until you move (L1-L2) nodes. At this point both the nodes are equidistant from the first intersecting common node. Now Traverse both the list one node at a time and compare the nodes at each step until you find a match. This matching node is the intersecting node.

----------------------------------------------------------------------------------------