getIntersectionNodeWithInfo<T> function

Map<String, dynamic> getIntersectionNodeWithInfo<T>(LinkedListNode<T>? headA, LinkedListNode<T>? headB)

Finds the intersection point and returns additional information

headA - The head of the first linked list headB - The head of the second linked list Returns a map containing intersection node and lengths

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

Implementation

Map<String, dynamic> getIntersectionNodeWithInfo<T>(
  LinkedListNode<T>? headA,
  LinkedListNode<T>? headB,
) {
  if (headA == null || headB == null) {
    return {
      'intersectionNode': null,
      'lengthA': 0,
      'lengthB': 0,
      'hasIntersection': false,
    };
  }

  int lenA = getLength(headA);
  int lenB = getLength(headB);

  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;
    }
  }

  LinkedListNode<T>? intersectionNode;
  while (currentA != null && currentB != null) {
    if (currentA == currentB) {
      intersectionNode = currentA;
      break;
    }
    currentA = currentA.next;
    currentB = currentB.next;
  }

  return {
    'intersectionNode': intersectionNode,
    'lengthA': lenA,
    'lengthB': lenB,
    'hasIntersection': intersectionNode != null,
  };
}