# Objective

Given the heads of two linked lists, find the node where they converge; if no such node is found, return `null` instead.

# Observations

1. To determine whether or not the two lists converge, we need to compare the nodes in the two lists.
2. The first node in either list that also appears on the other list is the node where the lists converge.
3. The two lists do not converge if they both contain distinct nodes.
Code
``````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
// 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;
}
}``````