import java.util.*;

/**
*	Find the intersection point of two converging linked lists.
**/
class Solution {
	
	/**
	*	@param ListNode head The head of a linked list
	*	
	*	@return The number of nodes in the list 
	**/
	public static int getLength(ListNode head) {
		// List length
		int length = 0;
		// A pointer that walks through the list
		ListNode tmp = head;
		
		// If the current node exists
		while (tmp != null) {
			// Increment the counter
			length++;
			// Move forward to next node
			tmp = tmp.next;
		}
		
		// Return the length of the list
		return length;
	}
	
	public static ListNode getConvergentNode(ListNode headA, ListNode headB) {
		// Get the length of both lists
		int lengthA = getLength(headA);
		int lengthB = getLength(headB);
		
		// Create pointers to reference the heads of both lists
		ListNode tmpA = headA;
		ListNode tmpB = headB;
		
		// If list A is shorter, skip over the extra leading nodes in list B
		while (lengthA < lengthB) { 
			lengthB--; 
			tmpB = tmpB.next; 
		} // End once the lists at the end of both pointers are the same length 
		
		// If list B is shorter, skip over the extra leading nodes in list A 
		while (lengthA > lengthB) {
			lengthA--;
			tmpA = tmpA.next;
		} // End once the lists at the end of both pointers are the same length
		
		// Now that both list heads are pointing to the same number of nodes, 
		// walk the pointers forward until they match
		// We only need to check one node because the lists have the same length
		while (tmpA != null) {
			// If the two references point to the same node
			if (tmpA == tmpB) {
				// Return one of the references
				return tmpA;
			}
			
			// Walk pointers forward
			tmpA = tmpA.next;
			tmpB = tmpB.next;
		}
		
		// No intersection found
		return null;	
	}
	
	/**
	*	@param ListNode headA The head of the first list
	*	@param ListNode headB The head of the second list
	*
	*	@return A reference to the node where the two lists converged
	*			or null if they don't intersect
	**/
	public static ListNode getConvergentNodeSet(ListNode headA, ListNode headB) {
		// Pointers to the list heads
		ListNode tmpA = headA;
		ListNode tmpB = headB;
		
		// A set of all the nodes in one of the lists
		Set traversedNodes = new HashSet();
		
		// Use one pointer to iterate through the first list
		while (tmpA != null) {
			// Add each node to the set
			traversedNodes.add(tmpA);
			// Walk pointer forward
			tmpA = tmpA.next;
		}
		
		// Use the other pointer to iterate through the second list
		// to find the first already seen node
		while (tmpB != null) {
			// If current node was already seen when traversing listA
			if (traversedNodes.contains(tmpB)) {
				// The point of convergence was found, return the node
				return tmpB;
			}
			
			// Walk pointer forward
			tmpB = tmpB.next;
		}
		
		// No intersection found
		return null;
	}
}

class ListNode {
	/* The data value stored within the node */
	E data;
	/* A reference to the next element in the list */
	ListNode next;
	
	ListNode(E data) {
		this.data = data;
		this.next = null;
	}
}