Intersection of Two Linked Lists - C Solution

1. Introduction

This blog post delves into a common problem in data structures using C programming: identifying the intersection point of two singly linked lists. This challenge is pivotal in understanding linked list operations and is particularly relevant in contexts where data sets are interconnected.

Problem

Given the heads of two singly linked lists, headA and headB, the task is to find and return the node where the two lists intersect. If there is no intersection, the function should return null. This problem tests our ability to manipulate and traverse linked lists.

2. Solution Steps

1. Traverse both lists to find their lengths.

2. Find the length difference between the two lists.

3. Advance the pointer in the longer list by the length difference.

4. Traverse both lists simultaneously until a common node is found or the end of either list is reached.

3. Code Program

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

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

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

// Function to find the intersection node of two linked lists
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int lengthA = getListLength(headA); // Length of list A
    int lengthB = getListLength(headB); // Length of list B
    int diff = abs(lengthA - lengthB); // Difference in lengths

    // Advance the pointer in the longer list by the length difference
    if (lengthA > lengthB) {
        while (diff--) headA = headA->next;
    } else {
        while (diff--) headB = headB->next;
    }

    // Traverse both lists simultaneously to find the intersection
    while (headA != NULL && headB != NULL) {
        if (headA == headB) return headA; // Intersection found
        headA = headA->next;
        headB = headB->next;
    }
    return NULL; // No intersection
}

// Utility function to create a new node
struct ListNode* newNode(int val) {
    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to demonstrate getIntersectionNode function
int main() {
    // Create two sample lists with intersection
    // List A: 1->2->3
    // List B: 4->5
    // Intersection at node with value 3
    struct ListNode* headA = newNode(1);
    headA->next = newNode(2);
    headA->next->next = newNode(3);

    struct ListNode* headB = newNode(4);
    headB->next = newNode(5);
    headB->next->next = headA->next->next; // Intersection point

    struct ListNode *result = getIntersectionNode(headA, headB); // Call the function
    if (result != NULL) {
        printf("Output: Intersection at node with value %d\n", result->val); // Print the result
    } else {
        printf("Output: No intersection\n");
    }

    // Free the lists
    free(headA->next->next); // Free intersection node
    free(headA->next); // Free rest of nodes in list A
    free(headA);
    free(headB->next); // Free nodes in list B (excluding intersection node)
    free(headB);

    return 0;
}

Output:

Intersection at node with value 3

Explanation:

The program first calculates the lengths of both linked lists. 

It then advances the pointer in the longer list by the difference in lengths, so that both pointers are equidistant from the end of their respective lists. 

It then simultaneously traverses both lists until a common node is found, indicating the intersection. 

In the example, lists A (1->2->3) and B (4->5->3) intersect at the node with value 3. Hence, the output is 'Intersection at a node with value 3'. 

This approach efficiently finds the intersection point without modifying the original lists.