(LINKEDLIST)getintersectionoftwolinkedlist.cpp

// C program to get intersection point of two linked list
#include <stdio.h>
#include <stdlib.h>

/* Link list node */
struct Node {
	int data;
	struct Node* next;
};

/* Function to get the counts of node in a linked list */
int getCount(struct Node* head);

/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct Node* head1, struct Node* head2);

/* function to get the intersection point of two linked
lists head1 and head2 */
int getIntesectionNode(struct Node* head1, struct Node* head2)
{
	int c1 = getCount(head1);
	int c2 = getCount(head2);
	int d;

	if (c1 > c2) {
		d = c1 - c2;
		return _getIntesectionNode(d, head1, head2);
	}
	else {
		d = c2 - c1;
		return _getIntesectionNode(d, head2, head1);
	}
}

/* function to get the intersection point of two linked
lists head1 and head2 where head1 has d more nodes than
head2 */
int _getIntesectionNode(int d, struct Node* head1, struct Node* head2)
{
	int i;
	struct Node* current1 = head1;
	struct Node* current2 = head2;

	for (i = 0; i < d; i++) {
		if (current1 == NULL) {
			return -1;
		}
		current1 = current1->next;
	}

	while (current1 != NULL && current2 != NULL) {
		if (current1 == current2)
			return current1->data;
		current1 = current1->next;
		current2 = current2->next;
	}

	return -1;
}

/* Takes head pointer of the linked list and
returns the count of nodes in the list */
int getCount(struct Node* head)
{
	struct Node* current = head;
	int count = 0;

	while (current != NULL) {
		count++;
		current = current->next;
	}

	return count;
}

/* IGNORE THE BELOW LINES OF CODE. THESE LINES
ARE JUST TO QUICKLY TEST THE ABOVE FUNCTION */
int main()
{
	/*
	Create two linked lists

	1st 3->6->9->15->30
	2nd 10->15->30

	15 is the intersection point
*/

	struct Node* newNode;
	struct Node* head1 = (struct Node*)malloc(sizeof(struct Node));
	head1->data = 10;

	struct Node* head2 = (struct Node*)malloc(sizeof(struct Node));
	head2->data = 3;

	newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = 6;
	head2->next = newNode;

	newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = 9;
	head2->next->next = newNode;

	newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = 15;
	head1->next = newNode;
	head2->next->next->next = newNode;

	newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = 30;
	head1->next->next = newNode;

	head1->next->next->next = NULL;

	printf("\n The node of intersection is %d \n",
		getIntesectionNode(head1, head2));

	getchar();
}