# C Exercises: Find the intersection of two singly linked lists

## C Singly Linked List : Exercise-19 with Solution

Write a C program to find the intersection of two singly linked lists.

**Sample Solution:**

**C Code:**

```
#include<stdio.h>
#include <stdlib.h>
// Define a structure for a Node in a singly linked list
struct Node {
int data;
struct Node* next;
};
// Function to create a new node with given data
struct Node* newNode(int data) {
// Allocate memory for a new node
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
// Set the data for the new node
node->data = data;
// Set the next pointer of the new node to NULL
node->next = NULL;
return node;
}
// Function to find the intersection node of two linked lists
struct Node* getIntersection(struct Node* head1, struct Node* head2) {
int count1 = 0, count2 = 0;
struct Node *curr1 = head1, *curr2 = head2;
// Count the number of nodes in each list
while (curr1) {
count1++;
curr1 = curr1->next;
}
while (curr2) {
count2++;
curr2 = curr2->next;
}
// Reset the pointers to the heads of the lists
curr1 = head1;
curr2 = head2;
// Adjust the pointers of the larger list to have the same number of nodes as the smaller list
if (count1 > count2) {
int i;
for (i = 0; i < count1 - count2; i++)
curr1 = curr1->next;
} else {
int i;
for (i = 0; i < count2 - count1; i++)
curr2 = curr2->next;
}
// Move both pointers together until they meet at the intersection
while (curr1 && curr2) {
if (curr1 == curr2)
return curr1; // Intersection found
curr1 = curr1->next;
curr2 = curr2->next;
}
// If there is no intersection, return NULL
return NULL;
}
// Function to display the elements of a linked list
void displayList(struct Node* head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
// Main function where the execution starts
int main() {
// Creating two linked lists
struct Node* head1 = newNode(1);
head1->next = newNode(2);
head1->next->next = newNode(3);
head1->next->next->next = newNode(4);
struct Node* head2 = newNode(5);
head2->next = head1->next->next;
printf("Original lists:\n");
displayList(head1);
displayList(head2);
// Finding intersection in the first pair of lists
struct Node* intersection1 = getIntersection(head1, head2);
if (intersection1)
printf("Intersection found at %d.\n", intersection1->data);
else
printf("Intersection not found.\n");
// Creating another pair of linked lists
struct Node* head3 = newNode(1);
head3->next = newNode(2);
head3->next->next = newNode(3);
head3->next->next->next = newNode(4);
struct Node* head4 = newNode(5);
head4->next = newNode(3);
head4->next->next = newNode(4);
printf("\nOriginal lists:\n");
displayList(head3);
displayList(head4);
// Finding intersection in the second pair of lists
struct Node* intersection2 = getIntersection(head3, head4);
if (intersection2)
printf("Intersection found at %d.\n", intersection2->data);
else
printf("Intersection not found.\n");
return 0; // Indicates successful completion of the program
}
```

Sample Output:

Original lists: 1 2 3 4 5 3 4 Intersection found at 3. Original lists: 1 2 3 4 5 3 4 Intersection not found.

**Flowchart : **

**C Programming Code Editor:**

**Previous:** Copy of a singly linked list with random pointers.

**Next:** Nodes from the end of a singly linked list.

**What is the difficulty level of this exercise?**

**Weekly Trends and Language Statistics**- Weekly Trends and Language Statistics