Find where two linked lists merge

© Parineeth M R

Question 8. Two linked lists merge at a common node. Given the heads of the two linked lists, find the node where the linked lists merge. For instance, the two linked lists ABCXYZ and PQXYZ merge at node X


Using a brute force approach, we can pick each node in the first linked list and compare it with every node in the second linked list in sequential order. If we get a match, then we have found the first common node between the two linked lists. If one linked list has m nodes and the other has n nodes, this takes O(mn) time.
However there are better techniques to solve the problem. Two approaches which can perform better than the brute force approach are described below

Approach 1: Marking the nodes
An extra field is maintained in each node to indicate if the node has been visited or not. Initially the nodes in both linked lists have the field set to 0 indicating that they have not yet been visited. The nodes of the first linked list are then traversed and the visited field in the first linked list nodes is set to 1 indicating that they have been visited. Then the nodes of the second linked list are traversed in sequential order. As soon as we encounter a node in the second linked list with the visited field set to 1, we have found the first node that is common to both the linked lists. The time taken by this approach is O(m+n) and it requires additional space in each node to store the visited field

Approach 2: Counting
The lengths of the two linked lists are first computed. Let m be the number of nodes in the longer linked list and n be the number of nodes in the shorter linked list. n1 is made to point to the head of the longer linked list and n2 is made to point to the head of the shorter linked list. The absolute difference in the lengths of the two linked lists m-n is then computed. n1 is advanced in the longer linked list by m-n nodes. Now the number of remaining nodes starting from n1 in the longer linked list is equal to the number of nodes in the shorter linked list. If n1 and n2 point to the same node, we have found the first common node. If not, we advance n1 and n2 by one node in their respective linked lists and compare them. This process is repeated till we get a match or we reach the end of the linked lists. The time taken by this approach is also O(m+n) and requires no additional space. So this approach is the preferred solution and is given below.

C/C++


/*
head1: first node of linked list1
head2: first node of linked list2
Return value: first common node between the two linked lists
*/
struct node * find_intersection_node(struct node * head1, struct node *head2)
{
	struct node *n1, *n2;
	int length1, length2, diff;

	/*Find the length of the two linked lists*/
	length1 = find_length(head1);
	length2 = find_length(head2);

	/*store head of the longer linked list in n1 and head of shorter 
	linked list in n2*/
	if (length1 >= length2) {
		n1 = head1;
		n2 = head2;
	} else {
		n1 = head2;
		n2 = head1;
	}

	/*Find the difference in length of the two linked lists. Then advance
	n1 by the difference*/
	diff = abs(length1 - length2);
	while (diff > 0) {
		n1 = n1->next;
		--diff;
	}

	/*Go on comparing the nodes in linked list1 starting from n1 and
	linked list2 starting from n2 till n1 and n2 match*/
	while (n1 && n2 && n1 != n2) {
		n1 = n1->next;
		n2 = n2->next;
	}

	/*n1 will have the common node if it exists, otherwise n1 will be NULL*/
	return n1;
}


Java


/*
head1: first node of linked list1
head2: first node of linked list2
Return value: first common node between the two linked lists
*/
public static LinkedListNode findIntersectionNode(LinkedListNode head1, 
				LinkedListNode head2) {
	/*Find the length of the two linked lists*/
	int length1 = findLength(head1);
	int length2 = findLength(head2);
	LinkedListNode n1, n2;

	/*store head of the longer linked list in n1 and head of 
	shorter linked list in n2*/
	if (length1 >= length2) {
		n1 = head1;
		n2 = head2;
	} else {
		n1 = head2;
		n2 = head1;
	}

	/*Find the difference in length of the two linked lists. Then advance
	n1 by the difference*/
	int diff = Math.abs(length1 - length2);
	while (diff > 0) {
		n1 = n1.next;
		--diff;
	}

	/*Go on comparing the nodes in linked list1 starting from n1 and
	linked list2 starting from n2 till n1 and n2 match*/
	while (n1 != null && n2 != null && n1 != n2) {
		n1 = n1.next;
		n2 = n2.next;
	}

	/*n1 will have the common node if it exists, otherwise n1 will be null*/
	return n1;
}



Python


#head1: first node of linked list1
#head2: first node of linked list2
#Return value: first common node between the two linked lists 
@staticmethod
def find_intersection_node(head1, head2):
	#Find the length of the two linked lists
	length1 = LinkedListNode.find_length(head1)
	length2 = LinkedListNode.find_length(head2)

	#store head of the longer linked list in n1 and head of 
	#shorter linked list in n2
	if (length1 >= length2) :
		n1 = head1
		n2 = head2
	else :
		n1 = head2
		n2 = head1
	
	#Find the difference in length of the two linked lists. Then advance
	#n1 by the difference
	diff = abs(length1 - length2)
	while (diff > 0) :
		n1 = n1.next
		diff = diff - 1
	
	#Go on comparing the nodes in linked list1 starting from n1 and
	#linked list2 starting from n2 until n1 and n2 match
	while (n1 and n2 and n1 != n2) :
		n1 = n1.next
		n2 = n2.next
	
	#n1 will have the common node if it exists, otherwise n1 will be None
	return n1