getIntersectionNode<T> function

LinkedListNode<T>? getIntersectionNode<T>(LinkedListNode<T>? headA, LinkedListNode<T>? headB)

Finds the intersection point of two linked lists

headA - The head of the first linked list headB - The head of the second linked list Returns the intersection node, or null if no intersection exists

Time Complexity: O(n + m) where n and m are the lengths of the lists Space Complexity: O(1)

Implementation

LinkedListNode<T>? getIntersectionNode<T>(
  LinkedListNode<T>? headA,
  LinkedListNode<T>? headB,
) {
  if (headA == null || headB == null) return null;

  // Calculate lengths of both lists
  int lenA = getLength(headA);
  int lenB = getLength(headB);

  // Move the longer list forward by the difference
  LinkedListNode<T>? currentA = headA;
  LinkedListNode<T>? currentB = headB;

  if (lenA > lenB) {
    for (int i = 0; i < lenA - lenB; i++) {
      currentA = currentA!.next;
    }
  } else if (lenB > lenA) {
    for (int i = 0; i < lenB - lenA; i++) {
      currentB = currentB!.next;
    }
  }

  // Move both pointers until they meet
  while (currentA != null && currentB != null) {
    if (currentA == currentB) {
      return currentA;
    }
    currentA = currentA.next;
    currentB = currentB.next;
  }

  return null;
}