Intersection Point in Y Shaped Linked Lists

Link:-

Description :-

Given two singly linked lists of size N and M, write a program to get the point where two linked lists intersect each other.

Example 1:

Input:
LinkList1 = 3->6->9->common
LinkList2 = 10->common
common = 15->30->NULL
Output: 15

The task is to complete the function which takes the pointer to the head of linklist1(head1) and linklist2(head2) as input parameters and returns data value of a node where two linked lists intersect. If linked list do not merge at any point, then it should return -1.

Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 100
1 <= value <= 1000

Solution:-

Step 1: Maintain a pointer which points to head of linkedlist1 and b pointer which points to head of linkedlist2.

Step 2 : If a pointer is null them set point a pointer to head of linkedlist2.If not, then move a pointer to next node.

Step 3 : If b pointer is null them set point a pointer to head of linkedlist1.If not, then move b pointer to next node.

Step 4: Continue step 2 and step 3 until a pointer is not equal to b pointer. Finally, return the value of data contained in node pointed by either a pointer or b pointer.

Below is the java solution for this problem:

class Intersect
{
public int intersectPoint(Node headA, Node headB){
Node a=headA;
Node b=headB;

while(a!=b){

if(a==null){
a=headB;
}else{
a=a.next;
}
if(b==null){
b=headA;
}else{
b=b.next;
}
}
return a.data;
}
}

--

--

--

Love writing technical articles

Love podcasts or audiobooks? Learn on the go with our new app.

CRYPTO BHARAT × NITROX

Using GitHub Actions For CI/CD with .NET Core 5 and AWS Elastic Beanstalk

Dawn of the Sylo Node

Google’s 3-Word Plan to Help Employees Avoid Burnout Is So Simple You Should Steal It

Why CSS Selectors are the most useful Selenium WebDriver locators?

Hard Links VS Soft Links in Linux: What’s the Difference

An anime photo of a boy’s surprised face

How to set padding for UITextField in Swift

Akita Basics 5: Tracing

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kriti Mittal

Kriti Mittal

Love writing technical articles

More from Medium

Java 學習記錄109 — Introduction to SQLite

How developers deal with the date and time in Java

Understanding Quicksort : A Short Guide to Understand quicksort better

Local variables with “var” since Java 10