Intersection of linked list

argus · February 10, 2021, 6:42am

each approach is showing TLE,what to do

mr.encoder · February 10, 2021, 7:51am

Hey @argus see if this is 2 merged linked list and bigger linked list has length 6 and shorter 5 then first find the difference which in this case is 1, the linked list which is bigger in size . In that linked list travel to that much node , here you will reach at 10th node.
Now one pointer is at 10th node and another is at 5th node, now increment node by node and return that node which proves ptr1==ptr2

Attaching code for reference

github.com

DivonilLiquid/Data-Structure-Algorithm/blob/master/Linked List/IntersectionofTwoLinkedLists.cpp

/**
Question:
Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:


begin to intersect at node c1.

 

Example 1:


Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
 

Example 2:

This file has been truncated. show original

mr.encoder · February 14, 2021, 3:26am

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.