Find Intersection Point of Two Linked Lists in C

This program demonstrates how to find the intersection point of two singly linked lists. The intersection point is where the two lists meet and become a single linked list onwards. This is a common problem in data structure interviews and understanding it deepens knowledge about linked list operations.

Program Explanation

The program is built around a linked list node structure and includes functions for appending nodes, finding the intersection point, and displaying the lists. The primary logic to find the intersection uses the two-pointer technique to manage different list lengths efficiently.

• struct Node: Represents each node in the linked list, containing an integer data and a pointer to the next node.
• appendNode: Adds a new node to the end of the list.
• getIntersectionNode: Detects the intersection point using a two-pointer strategy.
• printList: Displays the content of the linked list.

Source Code

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

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

// Function to add a node at the end of the linked list
void appendNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node* last = *head_ref;  // used for traversing the list

    new_node->data = new_data;  
    new_node->next = NULL;     

    if (*head_ref == NULL) {  // If the list is empty, then make the new node as head
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {  // Traverse till the last node
        last = last->next;
    }
    last->next = new_node;  // Change the next of last node
}

// Function to get the intersection node of two singly linked lists
struct Node* getIntersectionNode(struct Node* headA, struct Node* headB) {
    struct Node* ptr1 = headA;
    struct Node* ptr2 = headB;

    if (ptr1 == NULL || ptr2 == NULL) return NULL;

    while (ptr1 != ptr2) {
        ptr1 = ptr1 ? ptr1->next : headB;
        ptr2 = ptr2 ? ptr2->next : headA;
    }

    return ptr1;
}

// Function to print nodes in a given linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\\n");
}

int main() {
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* intersect = NULL;

    // Create first list
    appendNode(&head1, 1);
    appendNode(&head1, 2);
    appendNode(&head1, 3);
    struct Node* common = (struct Node*) malloc(sizeof(struct Node));
    common->data = 4;
    common->next = NULL;
    appendNode(&head1, 4);

    // Create second list
    appendNode(&head2, 5);
    head2->next->next = common;  // Create an intersection point

    printf("List 1: ");
    printList(head1);
    printf("List 2: ");
    printList(head2);

    intersect = getIntersectionNode(head1, head2);
    if (intersect != NULL)
        printf("The intersection node's data is: %d\\n", intersect->data);
    else
        printf("No intersection point detected.\\n");

    return 0;
}
        

Conclusion

The provided C program efficiently finds the intersection point of two singly linked lists. By using two pointers that compensate for the difference in list lengths, the solution ensures that each pointer traverses exactly the length of the two lists combined, thus meeting at the intersection point if one exists.