Intersection of Two Linked Lists in c++

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:

1. By intersection
2. 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 pointer 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:

2. By taking the difference

First we check if both the lengths of the list are same. If they are same, then we shall start incrementing the pointers one by one. At some point they will meet each other.

If any one of the list length is greater than the other, then we traverse the difference, then start comparing both the pointers.

Solution in C++

/*
* File     : get_intersection_node.cpp
* Author   : ajay.thousand@gmail.com
* Copyright: @ prodevelopertutorial.com
*/

#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