getIntersectionNodeOptimized<T> function

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

Finds the intersection point using length and two-pointer technique

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>? getIntersectionNodeOptimized<T>(
  LinkedListNode<T>? headA,
  LinkedListNode<T>? headB,
) {
  if (headA == null || headB == null) return null;

  // Calculate lengths and check if lists end with same node
  int lenA = 0, lenB = 0;
  LinkedListNode<T>? endA = headA;
  LinkedListNode<T>? endB = headB;

  while (endA!.next != null) {
    lenA++;
    endA = endA.next;
  }
  while (endB!.next != null) {
    lenB++;
    endB = endB.next;
  }

  // If they don't end with same node, no intersection
  if (endA != endB) return null;

  // Move the longer list forward
  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;
    }
  }

  // Find intersection
  while (currentA != currentB) {
    currentA = currentA!.next;
    currentB = currentB!.next;
  }

  return currentA;
}