CareerCup

check question?id=14952616

1. Create two iterators. Start a while loop looping through one of the iterators
2. increment the second iterator with each loop
3. If iterator1.next() == iterator2.next(), return that node.

Put the contents of the smaller list into a HashSet and then iterate over the larger list until you find an object that is contained in the HashSet.

public static T getFirstCommonElement(List<T> list1, List<T> list2){
	List<T> smallList, largeList;
	if(list1.size() < list2.size()){
		smallList = list1;
		largeList = list2;
	}
	else{
		smallList = list2;
		largeList = list1;
	}

	HashSet<T> set = new HashSet<T>(smallList.size());
	set.addAll(smallList);

	for(T obj : largeList){
		if(set.contains(obj)){
			return obj;
		}
	}
	return null;
}

if the list can be traversed both forwards and backwards... that should be enough of a hint to find out if they're merged in O(1) :)

Let two list be L1 and L2. Count the number of nodes in list L1, lets say its c1. Then reverse list L2( you can do it using three pointers). Again count number of nodes in L1, lets says count now is c2.

if(c1 == c2)
Lists do not merge
else
(c1 - c2) common nodes between L1 and L2.

All the operations are O(N) so overall time complexity is O(N).

Let two list be L1 and L2. Count the number of nodes in list L1, lets say its c1. Then reverse list L2( you can do it using three pointers). Again count number of nodes in L1, lets says count now is c2.

if(c1 == c2)
Lists do not merge
else
(c1 - c2) common nodes between L1 and L2.

All the operations are O(N) so overall time complexity is O(N).