C Exercises: Find the intersection of two singly linked lists

Last update on December 20 2024 13:18:41 (UTC/GMT +8 hours)

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.