Intersection of Two Linked Lists - CPP Solution

1. Introduction

In this blog post, we delve into a problem that involves finding the intersection point of two singly linked lists. This problem is a good test of understanding linked list traversal and comparison techniques.

Problem

Given the heads of two singly linked lists, headA and headB, the task is to return the node at which the two lists intersect. If the two linked lists do not intersect, return null.

2. Solution Steps

1. Traverse both lists to find their lengths.

2. Calculate the difference in lengths of the two lists.

3. Advance the pointer of the longer list by the difference in lengths.

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

5. Return the intersecting node if found; otherwise, return null.

3. Code Program

#include <iostream>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to find the length of the list
int getLength(ListNode *head) {
    int length = 0;
    while (head) {
        length++;
        head = head->next;
    }
    return length;
}

// Function to find the intersection node of two linked lists
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);

    // Align headA and headB
    while (lenA > lenB) {
        headA = headA->next;
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB->next;
        lenB--;
    }

    // Traverse the lists to find the intersection
    while (headA != headB) {
        headA = headA->next;
        headB = headB->next;
    }
    return headA; // Can be either headA or headB
}

int main() {
    // Creating two intersecting linked lists for demonstration
    // List A: 1 -> 2 -> 3 -> 4
    // List B: 5 -> 6 -> 4
    // Lists intersect at node with value 4
    ListNode *intersect = new ListNode(4);
    ListNode *headA = new ListNode(1);
    headA->next = new ListNode(2);
    headA->next->next = new ListNode(3);
    headA->next->next->next = intersect;

    ListNode *headB = new ListNode(5);
    headB->next = new ListNode(6);
    headB->next->next = intersect;

    ListNode *intersectionNode = getIntersectionNode(headA, headB);
    if (intersectionNode) {
        cout << "Intersection Node: " << intersectionNode->val << endl;
    } else {
        cout << "No intersection" << endl;
    }
    return 0;
}

Output:

Intersection Node: 4

Explanation:

The getIntersectionNode function first calculates the lengths of both lists. It then advances the head of the longer list by the difference in lengths to align both lists. 

Next, it traverses both lists simultaneously until it finds a common node, indicating the intersection point. If such a node is found, it is returned; otherwise, null is returned. 

This approach ensures that the intersection, if it exists, is found efficiently without modifying the structure of the lists.