Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- 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
- }
Add Comment
Please, Sign In to add comment