Intersection of Two Linked Lists Editorial

Practice Problem Link: Intersection of Two Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two linked lists, find the node at which they intersect. If the two lists do not intersect, return null.

Naive Approach

The simple solution is to use two nested loop. The outer loop will be for each node of the first list and the inner loop to compare all the node of the second list with the current node of the first list. If both the nodes are equal at some point then return that node otherwise return null.

Analysis

• Time Complexity: O(n * m)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

ListNode* getIntersectionNode(ListNode *A, ListNode *B) {
    ListNode* firstCurrNode = A;
	while (firstCurrNode != NULL) {
		ListNode* secondCurrNode = B;
		while (secondCurrNode != NULL) {
			if (firstCurrNode == secondCurrNode) {
				return firstCurrNode;
			}
			secondCurrNode = secondCurrNode->next;
		}
		firstCurrNode = firstCurrNode->next;
	}
	return NULL;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode getIntersectionNode(ListNode A, ListNode B) {
		ListNode firstCurrNode = A;
		while (firstCurrNode != null) {
			ListNode secondCurrNode = B;
			while (secondCurrNode != null) {
				if (firstCurrNode == secondCurrNode) {
					return firstCurrNode;
				}
				secondCurrNode = secondCurrNode.next;
			}
			firstCurrNode = firstCurrNode.next;
		}
		return null;
	}
}

Optimal Approach

Let's say the length of the two lists are length1 and length2 (length1 >= length2). Traverse the first list by a distance of length1 - length2 so that from here onwards both the list have an equal number of nodes. Now traverse both the lists simultaneously and compare the corresponding nodes. If two nodes are equal at some point then return that node otherwise return null.

Analysis

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

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/
ListNode* findIntersectionNode (ListNode *A, ListNode *B, int difference) {
	while(difference > 0) {
		A = A->next;
		difference--;
	}
	while (A != NULL && B!= NULL) {
		if (A==B) {
			return A;
		}
		A = A->next;
		B = B->next;
	}
	return NULL;
}
ListNode* getIntersectionNode(ListNode *A, ListNode *B) {
    int firstLength = 0;
	ListNode* firstCurrNode = A;
	while (firstCurrNode != NULL) {
		firstLength++;
		firstCurrNode = firstCurrNode->next;
	}
	int secondLength = 0;
	ListNode* secondCurrNode = B;
	while (secondCurrNode != NULL) {
		secondLength++;
		secondCurrNode = secondCurrNode->next;
	}
	if (firstLength < secondLength) {
		return findIntersectionNode (B, A, secondLength - firstLength);
	} else {
		return findIntersectionNode (A, B, firstLength - secondLength);
	}
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;

	ListNode(int data) {
		this.data = data;
		this.next = null;
	}
}
**/
class Solution {
	ListNode findIntersectionNode (ListNode A, ListNode B, int difference) {
		while(difference > 0) {
			A = A.next;
			difference--;
		}
		while (A != null && B!= null) {
			if (A==B) {
				return A;
			}
			A = A.next;
			B = B.next;
		}
		return null;
	}
	ListNode getIntersectionNode(ListNode A, ListNode B) {
		int firstLength = 0;
		ListNode firstCurrNode = A;
		while (firstCurrNode != null) {
			firstLength++;
			firstCurrNode = firstCurrNode.next;
		}
		int secondLength = 0;
		ListNode secondCurrNode = B;
		while (secondCurrNode != null) {
			secondLength++;
			secondCurrNode = secondCurrNode.next;
		}
		if (firstLength < secondLength) {
			return findIntersectionNode (B, A, secondLength - firstLength);
		} else {
			return findIntersectionNode (A, B, firstLength - secondLength);
		}
	}
}