C Exercises: Find the point at which two singly linked lists intersect

C Singly Linked List : Exercise-42 with Solution

Write a C program to find the point at which two singly linked lists intersect.

Sample Solution:

C Code:

#include<stdio.h>
#include <stdlib.h>


// Node definition
struct Node {
    int data;
    struct Node* next;
};

// Function to find the length of a linked list
int length(struct Node* head) {
    int len = 0;
    while (head != NULL) {
        len++;
        head = head->next;
    }
    return len;
}

// Function to find the intersection point of two linked lists
struct Node* findIntersection(struct Node* head1, struct Node* head2) {
    // Find the lengths of the linked lists
    int len1 = length(head1);
    int len2 = length(head2);

    // Traverse the longer linked list by the difference in length
    if (len1 > len2) {
        int diff = len1 - len2;
        for (int i = 0; i < diff; i++) {
            head1 = head1->next;
        }
    } else if (len2 > len1) {
        int diff = len2 - len1;
        for (int i = 0; i < diff; i++) {
            head2 = head2->next;
        }
    }

    // Traverse both lists until we find a node that is present in both lists
    while (head1 != NULL && head2 != NULL) {
        if (head1 == head2) {
            return head1;
        }
        head1 = head1->next;
        head2 = head2->next;
    }

    // If no intersection is found, return NULL
    return NULL;
}

void printList(Node* head) {
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Driver code
int main() {
    // Create two linked lists
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* common = (struct Node*)malloc(sizeof(struct Node));
    common->data = 7;
    common->next = NULL;
    head1 = (struct Node*)malloc(sizeof(struct Node));
    head1->data = 1;
    head1->next = (struct Node*)malloc(sizeof(struct Node));
    head1->next->data = 2;
    head1->next->next = common;
    printf("List-1: ");
	printList(head1);
    head2 = (struct Node*)malloc(sizeof(struct Node));
    head2->data = 3;
    head2->next = (struct Node*)malloc(sizeof(struct Node));
    head2->next->data = 4;
    head2->next->next = (struct Node*)malloc(sizeof(struct Node));
    head2->next->next->data = 5;
    head2->next->next->next = common;
    printf("List-2: ");
    printList(head2);
    // Find the intersection point
    struct Node* intersection = findIntersection(head1, head2);
    if (intersection == NULL) {
        printf("No intersection found.\n");
    } else {
        printf("Intersection found at node with data: %d\n", intersection->data);
    }

    struct Node* head3 = NULL;
    struct Node* head4 = NULL;
    struct Node* common1 = (struct Node*)malloc(sizeof(struct Node));
    common1->data = 5;
    common1->next = NULL;
    head3 = (struct Node*)malloc(sizeof(struct Node));
    head3->data = 1;
    head3->next = (struct Node*)malloc(sizeof(struct Node));
    head3->next->data = 2;
    head3->next->next = common1;
    printf("\nList-3: ");
	printList(head3);    
    head4 = (struct Node*)malloc(sizeof(struct Node));
    head4->data = 3;
    head4->next = (struct Node*)malloc(sizeof(struct Node));
    head4->next->data = 4;
    head4->next->next = (struct Node*)malloc(sizeof(struct Node));
    head4->next->next->data = 5;
    head4->next->next->next = common;
    printf("List-4: ");
	printList(head4);
    // Find the intersection point
    struct Node* intersection1 = findIntersection(head3, head4);
     if (intersection1 == NULL) {
        printf("No intersection found.\n");
      } else {
       printf("Intersection found at node with data: %d\n", intersection->data);
     }
    return 0;
}

Sample Output:

List-1: 1 2 7
List-2: 3 4 5 7
Intersection found at node with data: 7

List-3: 1 2 5
List-4: 3 4 5 7
No intersection found.

Flowchart :

C Programming Code Editor:

Previous: Reverse alternate k nodes of a singly linked list.
Next: C Programming Linked List Exercises Home