Find Intersection / join point of two single linked lists in java (example)

• Given two single linked lists, find out the intersection point of two single linked lists.
  • Traverse the single linked lists using non recursive or iterative algorithm.
• Suppose, we have two linked lists and they meets at certain point
  • then, we would like to find out the meeting or join point.
• We have shown two single linked lists, Linked list 1 and linked list 2 in Fig 1.
  • Both linked lists are intersected at node 50.
• As per our problem statement, we are interested in Node 50, where two linked lists intersects or joins together.

• Let us analyze the single linked lists shown in Fig 1
  1. Both single linked lists are joined together at node 50
  2. All the nodes after node 50 are common in both linked list (shown in green color).
  3. The nodes prior to node 50 differ in both the list i.e. length (or/and data) of lists varies prior to node 50.
• If we can able to find out the difference in length, prior to node 50, then we can figure out the join point of linked lists.

Algorithm – find intersection or join point of two single linked lists in java

• Find out the length of single linked list1 & list2
  • length of single linked list1 as shown in Fig 1 is 9
  • length of linked single linked list2 is 7
• Find out the differences of length of two linked lists
  • difference = length of larger list – length of smaller list
  • difference = 9 – 7 => 2
• So, we can reduce two nodes from larger linked list (i.e. Linked list 1)
  • then Linked list 1 will become equal to Linked list 2
  • Move the head pointer of larger list by 2
  • We have shown head1 reference shift by 2 in Fig 2
• Now, both head1 (pointing at Node 30) and head2 will travel equal nodes
  • i.e Both linked lists will travel 7 nodes
• Compare the address of both nodes during traversal
  • Address will be same at Node 50
  • So, Node 50 will be join point
• Got the join points of both linked lists

Time complexity of algorithm is O (n).

Program – find intersection or join point of two single linked lists in java

1.) IntersectionPoint Class:

• We are passing head of both single linked lists
• We are finding the join point by calling intersectionPoint method.

package org.learn.Question;

import org.learn.List.Node;

public class IntersectionPoint {
	public static Node intersectionPoint(Node head1, Node head2) {
		int length1 = length(head1);
		int length2 = length(head2);

		Node largerList = null;
		Node smallerList = null;
		if (length1 > length2) {
			largerList = head1;
			smallerList = head2;
		} else {
			largerList = head2;
			smallerList = head1;
		}
		return getIntersetPoint(largerList, smallerList, Math.abs(length1 - length2));
	}

	private static Node getIntersetPoint(Node largerList,Node smallerList,int lengthDifference) {
		int count = 0;
		while (count++ < lengthDifference) {
			largerList = largerList.next;
		}
		while (largerList != null && smallerList != null) {
			if (largerList == smallerList)
				return largerList;
			largerList = largerList.next;
			smallerList = smallerList.next;
		}
		return null;
	}

	public static int length(Node head) {
		int length = 0;
		while (head != null) {
			head = head.next;
			length++;
		}
		return length;
	}

	public static Node insert(Node head, int data) {
		while (head.next != null)
			head = head.next;
		head.next = new Node(data);
		return head.next;
	}

	public static void print(Node head) {
		while (head != null) {
			System.out.printf("%d ", head.data);
			head = head.next;
		}
		System.out.println("");
	}
}

2.) App Class:

• We are creating two single linked lists (head1 and head2) in main method.
• We will print single linked lists.
• Finding the join points of Y shaped linked lists

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.IntersectionPoint;

public class App {
	public static void main(String[] args) {
		// List 1 - 20 25 30 35 40
		int[] data1 = { 20, 25, 30, 35, 40 };
		Node head1 = new Node(data1[0]);
		Node lastNodeList1 = null;
		for (int count = 1; count < data1.length; count++) {
			lastNodeList1 = IntersectionPoint.insert(head1, data1[count]);
		}
		
		// List 2 - 3 6 9
		int[] data2 = { 3, 6, 9 };
		Node head2 = new Node(data2[0]);
		Node lastNodeList2 = null;
		for (int count = 1; count < data2.length; count++) {
			lastNodeList2 = IntersectionPoint.insert(head2, data2[count]);
		}

		// Common Nodes - 50 51 52 53
		int[] commonData = { 50, 51, 52, 53 };
		Node commonList = new Node(commonData[0]);
		for (int count = 1; count < commonData.length; count++) {
			IntersectionPoint.insert(commonList, commonData[count]);
		}
		
		// 20 25 30 35 40 50 51 52 53
		lastNodeList1.next = commonList;
		// 3 6 9 50 51 52 53
		lastNodeList2.next = commonList;
		System.out.println("1.) Single linked list 1 is :");
		IntersectionPoint.print(head1);
		System.out.println("2.) Single linked list 2 is :");
		IntersectionPoint.print(head2);

		Node intersectNode = IntersectionPoint.intersectionPoint(head1, head2);
		if (null != intersectNode) {
			System.out.printf("3.) Single linked lists-intersected at: %d", intersectNode.data);
		} else {
			System.out.println("3.) Single linked lists are not intersected");
		}
	}
}

3.) Node Class:

• Node class representing the node (s) of single linked lists.

package org.learn.List;

public class Node {
	public int data;
	public Node next;

	public Node(int num) {
		this.data = num;
		this.next = null;
	}
}

Output – intersection or join points of two single linked lists in java

1.) Single linked list 1 is :
20 25 30 35 40 50 51 52 53 
2.) Single linked list 2 is :
3 6 9 50 51 52 53 
3.) Single linked lists are intersected at: 50

Download Code – Intersection / join point of two single linked lists