Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
This problem can be solved in 2 ways:
- By intersection
- By taking the difference
1. By intersection
In this solution, we take 2 pointers.
P1 points to the head of list_1.
P2 points to the head of list_2.
Traverse both P1 and P2 step by step and check if they match at any point. If matches, then return the node.
While traversing, if any one of the pointers is null, then we assign the head pointer of the other list.
i.e if P1 -> next is null, then we assign P1 -> list_2 and vice versa.
Example:
Solution in C++
#include<iostream> using namespace std; struct Node { int data; struct Node* next; }; void display_list(struct Node **head_pointer) { // take a reference to head pointer for navigation struct Node *temp = *head_pointer; while(temp != NULL) { if(temp->next != NULL) printf("%d -> ", temp->data); else printf("%d", temp->data); //navigate to next pointer temp = temp->next; } printf("\n"); } Node *get_intersection_node_by_iterative(Node *list_a, Node *list_b) { Node *pointer_to_a = list_a; Node *pointer_to_b = list_b; if (pointer_to_a == NULL || pointer_to_b == NULL) return NULL; while (pointer_to_a != NULL && pointer_to_b != NULL && pointer_to_a != pointer_to_b) { pointer_to_a = pointer_to_a->next; pointer_to_b = pointer_to_b->next; if (pointer_to_a == pointer_to_b) return pointer_to_a; if (pointer_to_a == NULL) pointer_to_a = list_b; if (pointer_to_b == NULL) pointer_to_b = list_a; } return pointer_to_a; } Node *get_intersection_node_by_count_method(Node *list_a, Node *list_b) { if(!list_a || !list_b) return NULL; int countA = 1; int countB = 1; Node * pointer_to_a = list_a; Node * pointer_to_b = list_b; while(pointer_to_a->next) { countA++; pointer_to_a = pointer_to_a -> next; } while(pointer_to_b->next) { countB++; pointer_to_b = pointer_to_b -> next; } //move head to have same length if(countA>countB) { while(countA>countB) { list_a = list_a->next; countA--; } } else { while(countA<countB) { list_b = list_b -> next; countB--; } } //both heads move toward intersection while(list_a != list_b) { list_a = list_a -> next; list_b = list_b -> next; } return list_a; } int main() { /* Create two linked lists 1st 1->2->3->4->5 ^ | 2nd 6->7 4 is the intersection point */ struct Node* newNode; struct Node* list_1 = (struct Node*) malloc(sizeof(struct Node)); list_1->data = 1; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 2; list_1->next = newNode; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 3; list_1->next->next = newNode; struct Node* list_2 = (struct Node*) malloc(sizeof(struct Node)); list_2->data = 6; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 7; list_2->next = newNode; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 4; list_1->next->next->next = newNode; list_2->next->next = newNode; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 5; list_1->next->next->next->next = newNode; list_1->next->next->next->next->next = NULL; cout<<"List One = "<<endl; display_list(&list_1); cout<<"List Two = "<<endl; display_list(&list_2); //struct Node* result = get_intersection_node_by_iterative(list_1, list_2); struct Node* result = get_intersection_node_by_count_method(list_1, list_2); cout<<"Both the nodes intersect at the data = "<<result->data<<endl; }
Output:
List One = 1 -> 2 -> 3 -> 4 -> 5 List Two = 6 -> 7 -> 4 -> 5 Both the nodes intersect at the data = 4