Two linked lists (simple link, not double link) heads are given: headA, and headB; it is also given that the two lists intersect, thus after the intersection they have the same elements to the end. Find the first common element (without modifying the lists elements or using additional datastructures)

gistfile1.txt

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class HomeWork1b {

  private static <T> void findFirstSharedElement(LinkedList<T> linkA,
			LinkedList<T> linkB) {

		int offsetA = 0;
		int offsetB = 0;

		if (linkB.size() > linkA.size())
			offsetB = linkB.size() - linkA.size();
		else
			offsetA = linkA.size() - linkB.size();

		int i = offsetA;

		while (offsetA < linkA.size()) {
			if (linkA.get(offsetA) != (linkB.get(offsetB)))
				i = offsetA + 1;
			offsetA++;
			offsetB++;
		}

		System.out.println("The first overlapped element is :");
		System.out.println((i + 1) + "th of LinkedListA");
		System.out.println((i + 1 + offsetB - offsetA) + "th of LinkedListB");

	}

	public static void main(String... args) {

		LinkedList<Integer> linkA = new LinkedList<Integer>();
		LinkedList<Integer> linkB = new LinkedList<Integer>();

		Integer[] sharedElements = { 1, 2, 3, 4, 5 };
		List<Integer> sharedElementsList = Arrays.asList(sharedElements);

		linkA.add(7);
		linkA.add(8);
		linkA.addAll(sharedElementsList);

		linkB.add(9);
		linkB.add(10);
		linkB.add(11);
		linkB.add(12);
		linkB.add(13);
		linkB.addAll(sharedElementsList);

		long startTime = System.nanoTime();
		findFirstSharedElement(linkA, linkB);
		long endTime = System.nanoTime();
		System.out.println("Took(nanoSec):" + (endTime - startTime));

	}
}