Find the Intersection Point of Two Linked Lists in C++

This C++ program demonstrates an efficient technique to find the intersection point of two singly linked lists. The program uses a two-pointer approach that does not require additional memory for data structures like hash tables.

Program Code

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to get the count of nodes in a linked list
int getCount(ListNode* head) {
    int count = 0;
    ListNode* current = head;
    while (current != NULL) {
        count++;
        current = current->next;
    }
    return count;
}

// Function to get the intersection point of two linked lists
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    int countA = getCount(headA);
    int countB = getCount(headB);
    int d = countA - countB;

    ListNode* ptr1 = headA;
    ListNode* ptr2 = headB;

    if (d > 0) {
        while (d--) ptr1 = ptr1->next;
    } else {
        while (d++) ptr2 = ptr2->next;
    }

    while (ptr1 != NULL && ptr2 != NULL) {
        if (ptr1 == ptr2)
            return ptr1;
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }

    return NULL;
}

// Helper function to print the result
void printIntersection(ListNode* node) {
    if (node != NULL) {
        std::cout << "Intersection at node with value: " << node->val << std::endl;
    } else {
        std::cout << "No intersection found." << std::endl;
    }
}

int main() {
    // Create first list: 3->6->9->15->30
    ListNode* newListA = new ListNode(3);
    newListA->next = new ListNode(6);
    newListA->next->next = new ListNode(9);
    newListA->next->next->next = new ListNode(15);
    newListA->next->next->next->next = new ListNode(30);

    // Create second list: 10->15->30
    ListNode* newListB = new ListNode(10);
    newListB->next = new ListNode(15);
    newListB->next->next = new ListNode(30);

    // Set up intersection
    newListB->next->next = newListA->next->next->next;

    // Find and print intersection
    ListNode* intersectionNode = getIntersectionNode(newListA, newListB);
    printIntersection(intersectionNode);

    return 0;
}

Explanation of the Code

The program defines a ListNode structure and includes functions to count nodes and detect intersections. The getIntersectionNode function first determines the lengths of both lists. It then advances the pointer in the longer list by the difference in lengths, ensuring that both pointers traverse an equal number of nodes until the end of the lists. If they intersect, they will do so at the same node after moving past the length difference.

Conclusion

This program efficiently determines the intersection point of two linked lists using a two-pointer technique, ensuring no additional memory is used beyond the pointers needed for traversal.