Lecture 222:- Student Challenge Finding Intersecting point of two Linked List

To find the intersecting point of two linked lists, you can use the following approach:

1. Traverse both linked lists to find their lengths.
2. Calculate the difference in lengths (if any) between the two lists.
3. Start traversing from the head of the longer list, and advance the pointer by the difference in lengths.
4. Now, traverse both lists in parallel until the pointers meet.
5. The meeting point is the intersecting node (if any), or null if there is no intersection.

Here's the C++ implementation to find the intersecting point of two singly linked lists:

cppCopy code

#include <iostream> class ListNode { public:    int val;    ListNode* next;    ListNode(int val) : val(val), next(nullptr) {} }; class Solution { public:    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {        if (!headA || !headB)            return nullptr;        int lengthA = getLength(headA);        int lengthB = getLength(headB);        // Calculate the difference in lengths between the two lists        int diff = abs(lengthA - lengthB);        // Start from the head of the longer list        ListNode* ptrA = (lengthA >= lengthB) ? headA : headB;        ListNode* ptrB = (lengthA >= lengthB) ? headB : headA;        // Advance the pointer in the longer list by the difference in lengths        while (diff > 0) {            ptrA = ptrA->next;            diff--;        }        // Traverse both lists in parallel until the pointers meet        while (ptrA && ptrB) {            if (ptrA == ptrB)                return ptrA; // Found intersecting node            ptrA = ptrA->next;            ptrB = ptrB->next;        }        return nullptr; // No intersection found    }    int getLength(ListNode* head) {        int length = 0;        ListNode* current = head;        while (current) {            length++;            current = current->next;        }        return length;    } }; int main() {    // Create two linked lists with an intersection at node with value 8    ListNode* common = new ListNode(8);    ListNode* headA = new ListNode(4);    headA->next = new ListNode(1);    headA->next->next = common;    ListNode* headB = new ListNode(5);    headB->next = new ListNode(0);    headB->next->next = new ListNode(1);    headB->next->next->next = common;    Solution solution;    ListNode* intersect = solution.getIntersectionNode(headA, headB);    if (intersect) {        std::cout << "Intersecting node value: " << intersect->val << std::endl;    } else {        std::cout << "No intersection found." << std::endl;    }    // Clean up memory (Don't forget to delete allocated memory in a real application)    delete headA;    delete headB;    delete common;    return 0; }

In this implementation, the ListNode class is used to represent each node in the linked list. The Solution class contains the getIntersectionNode method, which finds the intersecting node of two linked lists.

In the main function, we create two linked lists (headA and headB) with an intersection at a common node with the value 8. We then use the getIntersectionNode method to find the intersecting node and print its value. The output will be Intersecting node value: 8, as both lists have an intersection at the node with value 8.