Home » Interview coding problems/challenges

# Intersection Point in Y-Shaped Linked List

In this article, we are going to see **how to find the intersection point in a Y-shaped linked list**? This problem has been featured in the coding round of Amazon, D.E Shaw and Goldman Sachs.

Submitted by Radib Kar, on February 13, 2019

**Problem statement:**

There are two singly linked lists where end nodes of one linked list got linked into the second list, forming aY (or 'T') shaped list. Write a program to get the point where two linked lists got merged.

**Example:**

1 → 2 → 3 → 6 ← 4 ← 5 ↓ 8 ↓ NULL

head1 is **1** and head2 is **5**, both have a common merged tail portion which is 6 -> 8 -> NULL. So the **intersection point is 6**.

**Solution:**

**Pre-requisite:**

- Set s to store linked list nodes.
- Two head pointers pointing to the Y('T') shaped linked list.

**Algorithm:**

1. Declare set 's' to store nodes of the linked list; 2. Declare and define two pointer to node type variable Node* temp1=head1,*temp2=head2 //for traversing 3. While(temp1){ //until the first linked list is traversed Insert all the nodes (pointer to nodes of course) to the set; //remember nodes to be entered not the data value Insert(s, temp1); temp1=temp1->next; END While 4. While(temp2) IF (if temp2 is not present in the set) //not part of merged tail temp2=temp2->next; Else return temp2->data; //first intersection point found End IF-ELSE End While

**Note:**

The nodes (pointer to nodes) are to be inserted into the set, not the node data. Let's say for an input example both heads have the same input data (for example say 1), but nodes are actually different (no intersection there). But if we maintain the set with node data, then that will return the 1, which is the wrong answer.

1 → 2 → 3 → 6 ← 4 ← 1 ↓ 8 ↓ NULL

For the above example, answer will be 1 if we start inserting node->data to the set instead of node. But the actual answer is 6.

**Explanation with example:**

The above algorithm is pretty simple and self-explanatory. Discussion for above example: After processing the first list the set contains: Pointer to Node having value 1 Pointer Node having value 2 Pointer to Node having value 3 Pointer Node having value 6 Pointer Node having value 8 NULL When second list is processed and checked, Pointer to node having value 1 is not in set (any doubt!Why? think yourself) Pointer to node having value 4 is not in set (No doubt) Pointer to node having value 6 is in the set (then what’s the difference between the first case where you have doubt!!! Reason is different address of the nodes though same value since those are different node, but in the second case the common node is same node) Thus it returns 6.

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; class Node{ public: int data; // data field Node *next;//next pointer }; Node* creatnode(int d){ Node* temp=(Node*)malloc(sizeof(Node)); temp->data=d; temp->next=NULL; return temp; } int intersectPoint(Node* head1, Node* head2) { set<Node*> s; Node* temp1=head1,*temp2=head2; while(temp1){ s.insert(temp1); temp1=temp1->next; } while(temp2){ if(s.find(temp2)==s.end()){ temp2=temp2->next; } else{ return temp2->data; } } return -1;//not at all a Y-shaped one } int main(){ cout<<"Linked list built like modified example\n"; Node* head1=creatnode(1); Node* head2=creatnode(1); head1->next=creatnode(2); head2->next=creatnode(4); head1->next->next=creatnode(3); head1->next->next->next=creatnode(6); head2->next->next=head1->next->next->next;//merged head1->next->next->next->next=creatnode(8); if(intersectPoint(head1,head2)==-1) cout<<"Not Y/T shapped at all"; else{ cout<<"intersection point is:"; cout<<intersectPoint(head1,head2)<<endl; } return 0; }

**Output**

Linked list built like modified example intersection point is:6

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL