 ### C++ program to find the intersection point of two linked lists

Algorithm:

The idea is to get a pointer to the loop node using Floyd’s cycle detection algorithm  and count the total number of nodes in the loop using that loop node, say `k`. Then take two pointers – one pointing to the head node and another pointing to the `kth` node from the head. If we simultaneously move these pointers at the same speed, they will eventually meet at the loop’s starting node.

Program:

#include <iostream>

#include <unordered_set>

using namespace std;

struct Node

{

int data;

Node* next;

};

// Utility function to create a new node with the given data and

// pushes it onto the list's front

{

// create a new linked list node from the heap

Node* newNode = new Node;

newNode->data = data;

}

// Find the starting node of the loop in a linked list pointed by `head`.

// The `loopNode` points to one of the nodes involved in the cycle

{

// find the count of nodes involved in the loop and store the count in `k`

int k = 1;

for (Node* ptr = loopNode; ptr->next != loopNode; ptr = ptr->next) {

k++;

}

// get pointer to k'th node from the head

for (int i = 0; i < k; i++) {

curr = curr->next;

}

// simultaneously move the `head` and `curr` pointers

// at the same speed until they meet

{

curr = curr->next;

}

// `curr` now points to the starting node of the loop

return curr;

}

// Function to identify a cycle in a linked list using

// Floyd’s cycle detection algorithm

{

// take two pointers – `slow` and `fast`

while (fast && fast->next)

{

// move slow by one pointer

slow = slow->next;

// move fast by two pointers

fast = fast->next->next;

// if they meet any node, the linked list contains a cycle

if (slow == fast) {

return slow;

}

}

// return null if the linked list does not contain a cycle

return nullptr;

}

// Function to find the intersection point of two linked lists

Node* findIntersection(Node* first, Node* second)

{

Node* prev = nullptr;       // previous pointer

Node* curr = first;         // main pointer

// traverse the first list

while (curr)

{

// update the previous pointer to the current node and

// move the main pointer to the next node

prev = curr;

curr = curr->next;

}

// create a cycle in the first list

if (prev) {

prev->next = first;

}

// now get a pointer to the loop node using the second list

Node* slow = identifyCycle(second);

// find the intersection node

if (slow) {

}

// remove cycle in the first list before exiting

if (prev) {

prev->next = nullptr;

}

// return the intersection node

}

int main()

{

// construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)

Node* first = nullptr;

for (int i = 7; i > 0; i--) {

push(first, i);

}

// construct the second linked list (1 —> 2 —> 3 —> null)

Node* second = nullptr;

for (int i = 3; i > 0; i--) {

push(second, i);

}

// link tail of the second list to the fourth node of the first list

second->next->next->next = first->next->next->next;

cout << "The intersection point is " << addr->data << endl;

}

else {

cout << "The lists do not intersect." << endl;

}

return 0;

}

Output:

The intersection point is 4 #### More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 394 1
C++ program to Sort a Linked List Using Merge Sort 358 1
C++ Program to Implement a Linked List representation of a Binary tree 353 1
C++ Program to Check for balanced parentheses in an expression 251 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 289 1
C++ program to print Indian flag 385 1
C++ program to Convert a multi level linked list to a singly linked list 269 1
C++ program to print right view of a Binary tree using queue 243 1
C++ Program to implement Huffman Coding Compression Algorithm 1660 1
C++ Program to Create a Height Balanced Binary Tree 274 1
C++ program to implement Prims algorithm 635 1
C++ Program for BFS Traversal 288 1
C++ Progam to Evaluate a Prefix Expression 460 1
C++ Program to Implement Queue using Linked List 254 1
C++ implementation of Stack using Linked list 303 1
C++ program to find the intersection point of two linked lists 339 1
C++ program to count the inversions in the given array 278 1
C++ program to perform D.N.F sort 325 1
C++ program to print all possible subsets of a String 286 1
C++ program to count the number of ones in a binary representation of a number 310 1
C++ program to print all possible subsets of a set 322 1
C++ program to find the largest word in a String 287 1
C++ Program to print a matrix in Spiral order 365 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 312 1
C limits library 340 1
Program to add two Binary numbers 332 1