getIntersection.ts

/*
  Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. 
  Note that the intersection is defined based on reference not value. That is, if the kth node of the first 
  linked list is the exact same node (by reference) as the jth node of the second linked list, then they are 
  intersecting.
*/
function getIntersection(h1: Node, h2: Node) {
  const nodes1 = getNodesMap(h1)
  const nodes2 = getNodesMap(h2)

  let intersection = null
  nodes1.forEach(n => {
    if (nodes2.get(n)) {
      intersection = n
    }
    return n
  })

  return intersection
}


function getNodesMap(head: Node): Map<Node, Node> {
  const nodes = new Map()
  nodes.set(head, head)

  let node = head
  while (node.next) {
    node = node.next
    if (!nodes.get(node)) {
      nodes.set(node, node)
    } else {
      break // loop found
    }
  }

  return nodes
}