/*
  Problem Interpretation

  We have two linked lists that may intersect at some point. We need
  to find whether they share any common node (not just same value, but
  the same memory address / same node object).
  
   Optimal Solution: Two-Pointer Technique (O(m + n) time, O(1) space)
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

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

/*
         ptrA
           |
           v
          ---     ---     ---    
headA -->| 1 |-->| 2 |-->| 3 | 
          ---     ---     --- \
                               \
                                ----> ---     ---    
                                     | 8 |-->| 9 |-->null
                       -------------> ---     ---    
          ---     ---/
headB -->| 4 |-->| 5 |
          ---     ---
           ^
           |
          ptrB


ptrA: 1,2,3,8,9,4,5,8
ptrB: 4,5,8,9,1,2,3,8

*/

// Function to check if two lists intersect (share the same node)
bool hasIntersection(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return false;

    ListNode* ptrA = headA;
    ListNode* ptrB = headB;

    cout << format("ptrA   ptrB\n");    
    cout << format("----   ----\n");
    cout << format("1      4\n");
    

    // Traverse both lists. When one reaches end, switch to the other list's head
    while (ptrA != ptrB)
    {
        if (ptrA == nullptr)
            ptrA = headB;
        else        
            ptrA = ptrA->next;

        if (ptrB == nullptr)
            ptrB = headA;
        else        
            ptrB = ptrB->next;

        if (ptrA != nullptr && ptrB != nullptr)
            cout << format("{}      {}\n", ptrA->val, ptrB->val);
            
        // ptrA = (ptrA == nullptr) ? headB : ptrA->next;
        // ptrB = (ptrB == nullptr) ? headA : ptrB->next;
    }

    // If they meet at a non-null node → intersection exists
    // If they meet at nullptr → no intersection
    return ptrA != nullptr;
}

// Optional: Return the intersecting node itself (or nullptr if no intersection)
ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    if (!headA || !headB) return nullptr;

    ListNode* ptrA = headA;
    ListNode* ptrB = headB;

    while (ptrA != ptrB) {
        if (ptrA == nullptr)
            ptrA = headB;
        else        
            ptrA = ptrA->next;

        if (ptrB == nullptr)
            ptrB = headA;
        else        
            ptrB = ptrB->next;

        if (ptrA != nullptr && ptrB != nullptr)
            cout << format("{}      {}\n", ptrA->val, ptrB->val);
        
        // ptrA = (ptrA == nullptr) ? headB : ptrA->next;
        // ptrB = (ptrB == nullptr) ? headA : ptrB->next;
    }

    return ptrA;  // returns the first common node or nullptr
}

int main() {
    // Create common part
    ListNode* common = new ListNode(8);
    common->next = new ListNode(9);

    // List A: 1 -> 2 -> 3 -> 8 -> 9
    ListNode* headA = new ListNode(1);
    headA->next = new ListNode(2);
    headA->next->next = new ListNode(3);
    headA->next->next->next = common;

    // List B: 4 -> 5 -> 8 -> 9
    ListNode* headB = new ListNode(4);
    headB->next = new ListNode(5);
    headB->next->next = common;

    bool hasI = hasIntersection(headA, headB);
    cout << "---------\n";
    
    if (hasI)
    {
        cout << format("1      4\n");
        ListNode* node = getIntersectionNode(headA, headB);
        cout << "Lists intesect at node with value: " << node->val << endl;
    }
    else
        cout << "No intersection\n";    
    
    // if (hasIntersection(headA, headB)) {
    //     std::cout << "Lists intersect at node with value: " 
    //               << getIntersectionNode(headA, headB)->val
    //               << std::endl << std::endl;        
    // } else {
    //     std::cout << "No intersection" << std::endl;
    // }

    // TODO: proper memory cleanup in real code
    return 0;
}