Check Where Two Linked Lists meet

#1

PROBLEM:

Intersection point two linked lists

There are two linked lists. Due to some programming error, the end node of one of the linked list got linked into the second list, forming an inverted Y shaped list. Now it’s your job to find the point(Node) at which the two linked lists are intersecting.

MY APPROACH:

  1. join the head of one linked list with the tail of another
  2. check if cycle exists, IF NOT join tail of first list to head of another
  3. check if cycle exists, IF NOT return (no intersection point)
  4. Create the cycle
  5. Find starting point of cycle using a fast-moving and slow-moving pointer
  6. this point is intersection

HOW TO IMPLEMENT THIS? if it is right

What other approaches to try? Should we simply compare when linked lists start getting same values of nodes?

#2

Hey, yes it can be done using your approach and it can also be done by a very simple way… if you have the count of the no. of elements of the lists then you can determine where the lists are intersecting by taking the absolute difference of no. of elements of both the lists.
Steps :

  • Get count of the nodes in the first list, let count be c1.

  • Get count of the nodes in the second list, let count be c2.

  • Get the difference of counts d = abs(c1 – c2)

  • Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.

  • Then we can traverse both the lists in parallel till we come across a common node.

Should we simply compare when linked lists start getting same values of nodes? -> yes

1 Like
#3

The solution seems right.

But how do I implement my algorithm?

#4

https://ide.codingblocks.com/s/43147

Try completing this code and take hints from this.
Do let me know incase of any doubts.

#5

I know how to code for the algorithm given by @sanjeetboora but I wanted to implement the algo proposed by me in the question.