I had given a technical interview in which I have been asked to find intersection point of n link list. I could come up to find intersection point of 2 link list but couldn't extend it. Could someone help me reach the algorithm

I tried to call the function to find integration point of 2 link list for every pair, but that didn't work.

CodePudding user response：

To find the intersection point of n linked lists, you can use the following steps:

1. Create a map that maps each node in the linked lists to the number of linked lists it appears in.
2. Iterate through the linked lists and for each node, increment the count in the map for that node.
3. Iterate through the map and return the first node that appears in all n linked lists.

Here is an example of how this algorithm might be implemented in C :

#include <unordered_map>

struct ListNode
{
   int val;
   ListNode* next;
   ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* intersection(const vector<ListNode*>& lists)
{
   // Create a map that maps each node in the linked lists to the number of linked lists it appears in
   unordered_map<ListNode*, int> map;

   // Iterate through the linked lists and for each node, increment the count in the map for that node
   for (const auto& list : lists)
   {
      for (auto p = list; p; p = p->next)
      {
         map[p]  ;
      }
   }

   // Iterate through the map and return the first node that appears in all n linked lists
   for (const auto& [node, count] : map)
   {
      if (count == lists.size())
      {
         return node;
      }
   }

   // No intersection point was found
   return nullptr;
}

In this example, the intersection function takes a vector of linked lists as an argument and returns the intersection point of the linked lists (if one exists). It first creates a map that maps each node in the linked lists to the number of linked lists it appears in. Then, it iterates through the linked lists and for each node, increments the count in the map for that node.

Finally, the function iterates through the map and returns the first node that appears in all n linked lists. If no such node is found, the function returns nullptr.

CodePudding user response：

For finding intersection point of 2 link list:

1. Get the count of both the link list, suppose the bigger list is k nodes greater than second.
2. Traverse k nodes in the bigger link list, then then start comparing nodes of both the link list. If they match, then you have found the intersection point.

I had come up with this method to find the intersection of 2 link list, but I am somehow not able to extend it for 'n'. Could we extend this to find intersection of n link list, or do we have to use map based approach only.