Objective
Given the heads of two linked lists, find the node where they converge; if no such node is found, return null
instead.
Observations
- To determine whether or not the two lists converge, we need to compare the nodes in the two lists.
- The first node in either list that also appears on the other list is the node where the lists converge.
- 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
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;
}
}