{"id":3871,"date":"2021-08-16T13:18:50","date_gmt":"2021-08-16T13:18:50","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3871"},"modified":"2022-03-10T18:40:31","modified_gmt":"2022-03-10T18:40:31","slug":"intersection-point-of-two-linked-lists","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/intersection-point-of-two-linked-lists\/","title":{"rendered":"Intersection point of two linked lists"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

Given two singly linked lists, which may or may not intersect each other. Write a function to return the intersection point of the two linked lists. If they don\u2019t intersect, return NULL.<\/p>\n<\/p>\n

Problem Statement Understanding<\/h3>\n

What do we mean by the intersection of two linked lists?<\/p>\n

By intersection, we mean that the two linked lists merge into one linked list at some node. This means they will have some nodes common from the end.<\/p>\n

Example:<\/strong><\/p>\n

\"\"<\/p>\n

The above 2 linked lists intersect at the node having value 9.<\/p>\n

In this problem, we have to find this intersection point of the two given linked list.<\/p>\n

Now that we have understood what we have to do, think of how we can approach this problem?<\/p>\n

Approach 1 (Using hash-set)<\/h3>\n

One thing we can do is to traverse one of the linked lists and for each node check if it is present in the other linked list. And we return the first matching node as our intersection point.<\/p>\n

Now, how to check for the presence of a node in the linked list?<\/p>\n

One approach would be that to check for each node of one of the linked lists, we traverse through the other one completely.<\/p>\n

But this method would take a lot of time. So, can we do better to check the presence of a node?<\/p>\n

We can use a hash-set to store all nodes of the first linked list and check if any node of the second linked list is there or not. By doing so, we reduce the total time taken with the expense of extra space.<\/p>\n

Now that you have an idea of what we are going to do, before moving ahead, try to implement it yourself.<\/p>\n

Algorithm<\/h3>\n
    \n
  • Declare a hash-set.<\/li>\n
  • Insert all the nodes of one of the linked lists into the hash-set.<\/li>\n
  • Now, traverse the other linked list, and for each node check if it is present in the hash-set or not.<\/li>\n
  • If the node is present, then that is the required intersection point.<\/li>\n
  • If no node of the second linked list is found in the hash-set, then the two linked lists do not intersect.<\/li>\n<\/ul>\n

    Code Implementation<\/h3>\n\t\t\t\t\t\t