Find Intersection Point in Two Linked List

Objec­tive: Given Two linked list, check whether both list inter­sect each other, if yes then find the start­ing node of the intersection.

Inter­sec­tion point means end of one linked list is linked with some node in another linked list and it forms a Y shape.

Input: Two Linked List

Out­put: Inter­sec­tion Node or point

Exam­ple:

Find Intersection Point in Two Linked List

Find Inter­sec­tion Point in Two Linked List

Approach:

  • Find the length of both the linked lists say : a_len and b_len
  • Find the len­Diff = (a_len ~ b_len)
  • Tra­verse the longer linked list by lenDiff
  • Now tra­verse both the lists at the same time
  • Check whether nodes are same, if yes then we have found the inter­sec­tion point
  • If we reach the end of the link lists then there is no inter­sec­tion point.

Trick Solu­tion:

 Time Com­plex­ity : O(n) , Space Com­plex­ity : O(1)
Com­plete Code:


Out­put:

List A :
->1->10->20->30->40->50->60
List B :
->5->15->30->40->50->60
Intersection found at 30

You may also like...