Problem Statement

Given two singly linked lists that merge at some point, your task is to find the intersection node where the two lists converge. The two linked lists are referred to as 'Y-shaped' because they have distinct paths (tails) leading to a common point of convergence (the head of the Y).

Examples

List 1: 3 → 6 → 9 → 15 → 30
List 2: 10 → 15 → 30

The two linked lists intersect at node with value 15.

Approaches

1️⃣ Brute Force Approach

This is very simplest approach. In it address of every node of first linked list is checked in corresponding second linked list. If a match is found, it indicates the intersection point; otherwise, there is no intersection.

Approach:

Intersection between two linked lists means they share a common node.

What should be the common attribute for two linked lists?

The common attribute isn't just the node's value, but the node itself. Therefore, we need to identify the exact node that appears in both lists.

Process

1. Select one of the linked lists to compare against the other. In this approach, we use the second list.
2. Iterate through the nodes of the second list.
3. For each node in the second list, check if it is present in the first list by iterating through the first list.
4. If a node from the second list is found in the first list, it indicates the first intersection node.
5. If no matching node is found after iterating through both lists, it means there is no intersection, and we return null.

Code:

#include <iostream>
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:
    //Function to find the intersection node of two linked lists
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // Traverse the second list
        while (headB != NULL) {
            //For each node in the second list, 
            //Traverse the first list
            ListNode *temp = headA;
            while (temp != NULL) {
                //If the current node 
                //Of the first list is the 
                //Same as the current node of 
                //The second list
                if (temp == headB) 
                    //Intersection node
                    return headB;
                //Move to the next node 
                //In the first list
                temp = temp->next;
            }
            // Move to the next node 
            //In the second list
            headB = headB->next;
        }
        //No intersection found
        return NULL;
    }
};

// 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 the new node as the head
    if (head == NULL) {
        head = newNode;
        return;
    }
    // Otherwise, traverse to the end of the list
    ListNode* temp = head;
    while (temp->next != NULL) 
        temp = temp->next;
    // Insert the new node at the end of the list
    temp->next = newNode;
}

// Utility function to print the linked list
void printList(ListNode* head) {
    // Traverse the list
    while (head->next != NULL) {
        // Print the value of each node followed by an arrow
        cout << head->val << "->";
        head = head->next;
    }
    // Print the value of the last node
    cout << head->val << endl;
}

int main() {
    // Creation of the first list
    ListNode* head1 = NULL;
    insertNode(head1, 1);
    insertNode(head1, 3);
    insertNode(head1, 1);
    insertNode(head1, 2);
    insertNode(head1, 4);

    // Create an intersection
    ListNode* intersection = head1->next->next->next;

    // Creation of the second list
    ListNode* head2 = NULL;
    insertNode(head2, 3);
    head2->next = intersection;

    // Printing the lists
    cout << "List1: "; 
    printList(head1);
    cout << "List2: "; 
    printList(head2);

    // Checking if an intersection is present
    Solution sol;
    ListNode* answerNode = sol.getIntersectionNode(head1, head2);
    if (answerNode == NULL)
        cout << "No intersection\n";
    else
        cout << "The intersection point is " << answerNode->val << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(Mx N), where 'M' is the number of nodes in list A and 'N' is the number of nodes in list B. This is because, for each node in list B, we iterate through the entire list A to check if there is an intersection. In the worst-case scenario, if there is no intersection, this results in a nested loop structure where each node in list B is compared with every node in list A, leading to O(MxN) operations.
• Space Complexity: O(1)
  • Because no additional data structures are used that scale with the size of the input. So it has constant amount of space regardless of the size of the input lists.

2️⃣ Using HashMap

To find where two linked lists intersect, we can use a hash set to remember all the nodes from the first list. Then, as we go through the second list, we check if any node is already in the hash set. The first node that is found in the set is where the lists intersect.

Approach:

To enhance the time complexity of the brute-force method, we can utilize hashing, which provides an efficient way to search in constant time, O(1). The steps are as follows:

• Hashing List 1 Nodes: Traverse through the first linked list and hash the addresses of its nodes. This allows us to store each node's address in a hash set, providing a quick way to reference these nodes later.
• Searching in List 2: Traverse through the second linked list and check if any node's address is already present in the hash set. If a node from the second list is found in the hash set, it means that this node is the intersection point, and we return it. This efficiently identifies the intersection without the need for nested iterations.

Code:

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		unordered_map<ListNode*, int> m;
		while(headA != NULL){
			m[headA]++;
			headA = headA -> next;
		}
		while(headB != NULL){
			if(m[headB] > 0){
				return headB;
			}
			headB = headB -> next;
		}
		return NULL;
	}
};

OR:

#include <iostream>
#include <unordered_set>

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:
    // Function to find the intersection node of two linked lists
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // Create a hash set to store the nodes 
        //Of the first list
        unordered_set<ListNode*> nodes_set;
        
        //Traverse the first linked list 
        //And add all its nodes to the set
        while (headA != NULL) {
            nodes_set.insert(headA);
            headA = headA->next;
        }

        //Traverse the second linked list 
        //And check for intersection
        while (headB != NULL) {
            // If a node from the second list is found in the set,
            // It means there is an intersection
            if (nodes_set.find(headB) != nodes_set.end()) {
                return headB;
            }
            headB = headB->next;
        }

        // No intersection found, return NULL
        return NULL;
    }
};

// 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 the new node as the head
    if (head == NULL) {
        head = newNode;
        return;
    }
    
    // Otherwise, traverse to the end of the list
    ListNode* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    
    // Insert the new node at the end of the list
    temp->next = newNode;
}

// Utility function to print the linked list
void printList(ListNode* head) {
    // Traverse the list
    while (head->next != NULL) {
        // Print the value of each node followed by an arrow
        cout << head->val << "->";
        head = head->next;
    }
    // Print the value of the last node
    cout << head->val << endl;
}

int main() {
    // Creation of the first list
    ListNode* head1 = NULL;
    insertNode(head1, 1);
    insertNode(head1, 3);
    insertNode(head1, 1);
    insertNode(head1, 2);
    insertNode(head1, 4);

    // Create an intersection
    ListNode* intersection = head1->next->next->next;

    // Creation of the second list
    ListNode* head2 = NULL;
    insertNode(head2, 3);
    head2->next = intersection;

    // Printing the lists
    cout << "List1: "; 
    printList(head1);
    cout << "List2: "; 
    printList(head2);

    // Checking if an intersection is present
    Solution sol;
    ListNode* answerNode = sol.getIntersectionNode(head1, head2);
    if (answerNode == NULL) {
        cout << "No intersection\n";
    } else {
        cout << "The intersection point is " << answerNode->val << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N+M)
  • The reason for this time complexity is that we first iterate through all nodes in the first list, which takes O(N) time. After that, we iterate through all nodes in the second list, which takes O(M) time. Therefore, the total time complexity is O(N+M).
• Space Complexity: O(N)
  • The reason for this space complexity is that we use an unordered_set to store the addresses of all nodes in the first list. The space required for this set depends on the number of nodes in the first list, which is O(N).

3️⃣ Optimal Approach (Length Difference)

Intuition:

To find the intersection of two linked lists, we use the difference in their lengths to align their starting points and then traverse both lists simultaneously until we find the intersection node.

Approach:

To optimize the search for the intersection node, we align the starting points of the two linked lists based on their lengths. Here's the process:

1. Calculate the lengths of both linked lists.
2. Determine the positive difference between these lengths.
3. Advance the pointer of the longer list by this difference, thereby aligning both lists to the same remaining length.
4. Traverse both lists simultaneously from these aligned points. The first node where the pointers meet is the intersection node.

Code:

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		int n = 0;
		int m = 0;
		ListNode* ptr1 = headA;
		ListNode* ptr2 = headB;
		while(ptr1 != NULL){
			n++;
			ptr1 = ptr1 -> next;
		}
		while(ptr2 != NULL){
			m++;
			ptr2 = ptr2 -> next;
		}
		int t = abs(n - m);
		if(n > m){
			while(t){
				headA = headA -> next;
				t--;
			}
		}
		else{
			while(t){
				headB = headB -> next;
				t--;
			}
		}
		while(headA != NULL and headB != NULL){
			if(headA == headB){
				return headA;
			}
			headA = headA -> next;
			headB = headB -> next;
		}
		return NULL;
	}
};

OR:

/*
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) {
        if (!headA || !headB) {
            return nullptr; // No intersection if either list is empty
        }

        // Calculate the lengths of both lists
        int listACount = 0, listBCount = 0;
        ListNode* iterator = headA;
        while (iterator) {
            listACount++;
            iterator = iterator->next;
        }

        iterator = headB;
        while (iterator) {
            listBCount++;
            iterator = iterator->next;
        }

        // Find the difference in lengths
        int difference = abs(listACount - listBCount);

        // Align the starting points of both lists
        ListNode* longerList = listACount > listBCount ? headA : headB;
        ListNode* shorterList = listACount > listBCount ? headB : headA;

        // Advance the pointer of the longer list by the difference
        while (difference--) {
            longerList = longerList->next;
        }

        // Traverse both lists together and find the intersection point
        while (longerList && shorterList) {
            if (longerList == shorterList) {
                return longerList; // Intersection found
            }
            longerList = longerList->next;
            shorterList = shorterList->next;
        }

        return nullptr; // No intersection
    }
};

Complexity Analysis:

• Time Complexity: O(m + n)
• Space Complexity: O(1)

4️⃣ Two-Pointers

Intuition:

1. Cycle Creation: By connecting the tail of headA to its head, we create a cycle. If headB intersects with headA, headB will enter this cycle.
2. Cycle Detection: Using Floyd’s Tortoise and Hare algorithm allows us to detect this cycle. If the two pointers meet, it confirms the presence of an intersection.
3. Finding Intersection: Once a cycle is detected, resetting one pointer to the start of headB and moving both pointers step-by-step ensures they meet at the intersection node, providing the solution.

Approach:

In this approach, we can simply convert this problem into a loop problem.

1. Find the tail.
2. Connect the tail with any of the head which creates a loop.
3. Using the other head, find intersection point of the loop.
4. Undo the loop, by setting tail->next = NULL
5. Return the intersection node.

Code:

class Solution {
public:
	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
		ListNode *ptr1 = headA;
		ListNode *ptr2 = headB;
		while(ptr1 != ptr2){
			if(ptr1 == NULL){
				ptr1 = headB;
			}
			else{
				ptr1 = ptr1 -> next;
			}
			if(ptr2 == NULL){
				ptr2 = headA;
			}
			else{
				ptr2 = ptr2 -> next;
			}
		}
		return ptr1;
	}
};

Complexity Analysis:

• Time Complexity: O(m + n)
• Space Complexity: O(1)