160. Intersection of Linked Lists

Problem Link

LeetCode 160

Problem Statement

Given the heads of two singly linked lists, headA and headB, return the node at which the two lists intesrect. If there is no intersection, return nullptr.

The linked lists must retain their original structure after the function returns. You are not allowed to modify the structure of the input lists permanently.

Node Definition

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

Solution Approaches

Approach 1: Length Calculation with Reversal

This method involves reversing the lists to determine thier lengths and deduce the intersection point using arithmetic calculations.

1. Check if the last nodes of both lists are the same. If not, return nullptr.
2. Reverse each list and calculate their rsepective lengths.
3. Using the derived lengths, compute the intersection point based on the equations formed from the lengths of the unique and shared parts of the lists.

class Solution {
public:
    int traverseAndGetLength(ListNode*& head, bool reverse = false) {
        int length = 0;
        ListNode* previous = nullptr;
        ListNode* current = head;
        while (current != nullptr) {
            length++;
            ListNode* next = current->next;
            if (reverse) {
                current->next = previous;
            }
            previous = current;
            current = next;
        }
        head = previous;
        return length;
    }

    ListNode* getLastNode(ListNode* head) {
        while (head->next != nullptr) {
            head = head->next;
        }
        return head;
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (getLastNode(headA) != getLastNode(headB)) {
            return nullptr;
        }

        int lengthA = traverseAndGetLength(headA, true);
        int lengthB = traverseAndGetLength(headB, true);
        int combinedLength = traverseAndGetLength(headA, true);

        int offset = (lengthA + lengthB - combinedLength) / 2;
        ListNode* result = headA;
        while (offset--) {
            result = result->next;
        }
        return result;
    }
};

Approach 2: Two Pointers with Cycle Simulation

This approach simulates a cycle by traversing both lists using two pointers. When one pointer reaches the end, it jumps to the head of the other list. The intersection point is found when both pointers meet.

class Solution {
public:
    ListNode* getLastNode(ListNode* head) {
        while (head->next != nullptr) {
            head = head->next;
        }
        return head;
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (getLastNode(headA) != getLastNode(headB)) {
            return nullptr;
        }

        ListNode* pointerA = headA;
        ListNode* pointerB = headB;

        while (pointerA != pointerB) {
            pointerA = (pointerA == nullptr) ? headB : pointerA->next;
            pointerB = (pointerB == nullptr) ? headA : pointerB->next;
        }

        return pointerA;
    }
};