Intersection

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 intersection.

Solution

If two linked lists intersect, the last element of both lists will be the same. Observe the diagram below for proof. To identify if two linked lists intersect, we can compare their tails.

The problem states the linked lists are singly linked lists, so to find the tails we will need to iterate through each linked list. In order to find the itersecting node, we can iterate through the lists simultaneously until we find the intersection. However, we do need to know the offset between the lists (the difference in sizes) so that we offset the pointers by the appropriate amount.

Let’s build a function to return the tail, and the size, of a linked list.

def get_tail_and_size(node):
  size = 1

  while(node.next != None):
    size += 1
    node = node.next

  return (node, size)

Now we can find the tails fo the linked lists, and compare them. If they are equal, the lists intersect, and if not, the lists do not intersect. Using the size, we can determine the offset so that we can iterate through the lists simultaneously.

We need two more functions - the first of which will get the kth node of a linked list.

def get_kth_node(node, k):
  for i in range(k):
    node = node.next

  return node

The second function will accept two linked list nodes, and return a boolean indicating if they are intersecting, as well as the intersecting node.

def find_intersection(l1, l2):
  t1, s1 = get_tail_and_size(l1)
  t2, s2 = get_tail_and_size(l2)

  if(t1 != t2):
    return (False, None)

  offset = s2 - s1

  if(offset > 0):
    l2 = get_kth_node(l2, offset)
  elif(offset < 0):
    l1 = get_kth_node(l1, offset)


  while(l1 != l2) and (l1.next != None) and (l2.next != None):
    l1 = l1.next
    l2 = l2.next

  if(l1 != l2):
    return (False, None)
  else:
    return (True, l1)