#include <bits/stdc++.h>
using namespace std;

// Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};


class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *temp1 = headA;
        ListNode *temp2 = headB;
        int n1 = 0, n2 = 0;
        
        // Get the length of first linked list
        while(temp1 != NULL) {
            n1++;
            temp1 = temp1-> next;
        }
          
        // Get the length of second linked list
        while(temp2 != NULL) {
            n2++;
            temp2 = temp2-> next;
        } 

        // Traverse the longer list and bring the pointers to same level
        if(n1 < n2) return collisionPoint(headA, headB, n2 - n1);
        
        // otherwise
        return collisionPoint(headB, headA, n1 - n2);
    }   
    
private:
    // Function to get the collision point
    ListNode* collisionPoint(ListNode *smallerListHead, ListNode *longerListHead, int len) {
        ListNode *temp1 = smallerListHead;
        ListNode *temp2 = longerListHead;
        
        // Adjust the pointers to same level
        for(int i = 0; i < len; i++) temp2 = temp2-> next;
        
        while(temp1 != temp2) {
            temp1 = temp1-> next;
            temp2 = temp2-> next;
        }
        
        return temp1;
    }   
};


// Utility function to insert a node at the end of the linked list
void insertNode(ListNode* &head, int val) {
    // Create a new node with the given value
    ListNode* newNode = new ListNode(val);
    // If the list is empty, set