Friday, November 5, 2010

sharing lists.

Given 2 linked lists find intersection point(s) in the form of X (so the lists share only one element), or Y (so the lists share more than one element). How many other shapes can you have?

2 comments:

  1. If the linked list is singly linked list, then it cannot share more than one element.

    ReplyDelete
  2. The lists are either disjoint or they coverge and stay converged somewhere in a Y shape. The trick is to find where that Y convergence happens. I'm assuming you can't modify the list to hold a bit of data (or you could just set it like a trail of bread crumbs and notice when you've entered a node with the bit set.) I also assume you have limited storage (or you could just make a double linked copy of the sets, or a hash table for that matter.)
    Answer: start at each node and COUNT the distance to the last node, giving you two distances d1 and d2. Step the longer node forward (d2-d1) nodes (assuming d2 was the larger one.) Now you have a "Y" diagram but you know both forks of the Y have the same size. Step both nodes together, check for convergence, and repeat with pairwise steps until they converge.

    ReplyDelete