Intersection of Two Linked Lists ✅ Leetcode Solution | Data structure and Algorithms Hello World

This is the video under the series of DATA STRUCTURE & ALGORITHM in a LinkedList Playlist. In this video, we will understand the Problem Intersection of Two Linked Lists.

We also Provide courses on Competitive Programming and Data structure and Algorithms. Please see our Full Playlist on our Channel.

----------------------------------------------------------------------------------------

🟠 160. The intersection of Two Linked Lists
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
For example, the following two linked lists begin to intersect at node c1:
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
listA - The first linked list.
listB - The second linked list.
skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.
The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
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.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

----------------------------------------------------------------------------------------

*Follow me *

----------------------------------------------------------------------------------------

►Our Playlists on:-

------------------------------------------------------------------------

🌟 Please leave a LIKE ❤️ and SUBSCRIBE for more AMAZING content! 🌟

✨ Tags ✨
DSA playlist c++
Intersection of Two Linked Lists
Intersection of Two Linked Lists geeksforgeeks
linked list intersection
Sort Linkedlist hindi
Intersection of Two Linked Lists c++
LinkedList Hindi
Linked list Hindi playlist
linked list playlist java

Comment "#Princebhai" if you read this 😉😉
#linkedlist #dsalgo #faang

[knowsbetter]

I solved by both approach on my own just after only watching your logic. Thanks

[amanjindal]

Aur bhaiya mujhe phle list smjh nhi aata tha.. Jb se aapki playlist dekhi h.. Kaafi kuch feel hone lg gya ki kaise kya krna hota hai.. Thnx again ❤️🙏🏼

[TurpuAvinash]

i feel like you are soo under-rated bro.I like the way you explain the things in very simple way

[shaantyagi]

Bhaiya Maine aise kiya hai ( video dekhne se pehle kiya bhaiya)
Approach:
1. Phele dono ka size dekh lenge.
2.Fir do pointer ko headA and headB ke head ko point kara denge.
3. ab jo bada hoga usko (large size - small size) se aage badha denge .
4. ab fir se traverse karenge, aur agar dono equal hai toh woh hum return kar denge, other wise return NULL.
5. base case: agar koi bhi dono mai se NULL hua toh return NULL.

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB==NULL){
return NULL;
}

int count1=0, count2=0;
ListNode* temp1 = headA;
ListNode* temp2 = headB;

while(temp1!=NULL){
count1++;
temp1=temp1->next;
}

while(temp2!=NULL){
count2++;
temp2=temp2->next;
}
int k =0;
if(count1>count2){
k = count1-count2;
}
else{
k = count2-count1;
}
ListNode* first = headA;
ListNode* second = headB;
if(count1>count2){
while(k--){
first = first->next;
}
}
else if(count2>count1){
while(k--){
second = second->next;
}
}

while(first!=NULL && second!=NULL){
if(first==second){
return first;
}
first=first->next;
second = second->next;
}

return NULL;
}

[sandeepkumarg]

GREAT EXPLANATION BHAIYA JI..
Approach -1
unordered_set<ListNode*> hs; //approach 1 S.C = O(n); that why not good soln
while (headA != NULL) {
hs.insert(headA);
headA = headA->next;
}
while (headB) {
if (hs.find(headB) != hs.end()) {
return headB;
break;
}
headB = headB->next;
}
return NULL;

Approach -2
1. Phele dono ka size dekh lenge.
2.Fir do pointer ko headA and headB ke head ko point kara denge.
3. ab jo bada hoga usko (large size - small size) se aage badha denge .
4. ab fir se traverse karenge, aur agar dono equal hai toh woh hum return kar denge, other wise return NULL.
5. base case: agar koi bhi dono mai se NULL hua toh return NULL.

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA==NULL || headB==NULL){
return NULL;
}

int count1=0, count2=0;
ListNode* temp1 = headA;
ListNode* temp2 = headB;

while(temp1!=NULL){
count1++;
temp1=temp1->next;
}

while(temp2!=NULL){
count2++;
temp2=temp2->next;
}
int k =0;
if(count1>count2){
k = count1-count2;
}
else{
k = count2-count1;
}
ListNode* first = headA;
ListNode* second = headB;
if(count1>count2){
while(k--){
first = first->next;
}
}
else if(count2>count1){
while(k--){
second = second->next;
}
}

while(first!=NULL && second!=NULL){
if(first==second){
return first;
}
first=first->next;
second = second->next;
}

return NULL;
}

[happyharsh]

Thanks!


class Solution {
public:
int Length(ListNode *head){
int count = 0;
while(head != NULL){
count++;
head = head->next;
}
return count;
}
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//Appraoch 1
// unordered_set<ListNode*> hs; //approach 1 S.C = O(n); that why not good soln
// while (headA != NULL) {
// hs.insert(headA);
// headA = headA->next;
// }
// while (headB) {
// if (hs.find(headB) != hs.end()) {
// return headB;
// break;
// }
// headB = headB->next;
// }
// return NULL;

//Approach 2
int lenA = Length(headA);
int lenB = Length(headB);
ListNode *p1 = headA;
ListNode *p2 = headB;
if(lenA < lenB){
int diff = lenB-lenA;
while(diff--){
headB = headB->next;
}
p2 = headB;
}else{
int diff = lenA-lenB;
while(diff--){
headA = headA->next;
}
p1 = headA;
}
while(p1 != NULL and p2 != NULL){
if(p1 == p2){
return p1;
}
p1 = p1->next;
p2 = p2->next;
}
return NULL;

}
};

[rode_atharva]

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) {
return nullptr;
}

ListNode *meet = nullptr;
ListNode *temp = headA;
int lenA = 0;
while (temp) {
lenA++;
temp = temp->next;
}

temp = headB;
int lenB = 0;
while (temp) {
lenB++;
temp = temp->next;
}

int skipA = 0;
int skipB = 0;

if (lenA > lenB) {
skipA = lenA - lenB;
}
if (lenB > lenA) {
skipB = lenB - lenA;
}
temp = headA;
ListNode *temp2 = headB;
if (skipA) {
for (int i = 0; i < skipA; i++) {
temp = temp->next;
}
}
if (skipB) {
for (int i = 0; i < skipB; i++) {
temp2 = temp2->next;
}
}

while (temp && temp2) {
if (temp == temp2) {
return temp;
}
temp = temp->next;
temp2 = temp2->next;
}
return nullptr;
}
};

[amanjindal]

Amazing bhai.. 🔥
Bhai aur sawal laao ek se ek.. Linked list ki series m maja aa rha aapki..

[pavanreddy]

can we do this by reversing the list first and then comparing from last?

[anjalipatel]

Sir aaproach toh samjh aati h but can you help me ki ye code step wise kaise krte h mujhe steps samjh ni aate ki phle kya likhu