algorithm to find if two linked lists are intersected

Two different lists will be intersected when one node of a list points to the other list’s node.

The below diagram depicts the intersection of lists

How do you solve it:

• Get the difference of the two lists (In above diagram it is 5-4=1)
• Take a pointer to the bigger list and move it as many number of times as difference between the lists calculated above (bigger list with 5 nodes is moved 1 position forward with pointer1 pointing to 2)
• Take another pointer to the second list and start comparing node of first list with the node of the second list. (Take pointer2 pointing to 18)
• Whenever nodes are same we can say lists are intersected. (they get intersected at node 4)

Code:

/**
	 * Algorithm to detect the intersecting point of two lists
	 *
	 * @param s1 first list which is larger in size
	 * @param s2 second list
	 */
	public static void getIntersectPoint(SLLIntersection s1,SLLIntersection s2){
		int s1Len = s1.getLength(s1.root);
		int s2Len = s2.getLength(s2.root);

		int diff = s1Len-s2Len;
		System.out.println("Difference between two lists is "+diff);

		// Move the pointer in the larger list to diff places
		SLLNode s1List = s1.root;
		if((s1Len-s2Len)>0) {
			while((s1List != null) && diff>0){
				s1List = s1List.next;
				diff--;
			}
		}

		// Now check the point where the lists are intersecting
		// by checking each node in two lists simultaneously
		SLLNode s2List = s2.root;
		while(s1List != null && s1List.next != null) {
			if(s1List == s2List) {
				System.out.println("Intersection point is at "+s1List.value);
			}
			// increment the pointers
			s1List = s1List.next;
			s2List = s2List.next;
		}
	}

Output:

List1: 1 2 3 4 5
List2: 18 19 4 5
Difference between two lists is 1
Intersection point is at 4