Friday 29 June 2012

Co-joined Linked lists

You have two linked lists: A and B. A and B are co-joined at some node 'c'.

(A)--------
           (c) |------- (common part of both linked lists)
(B)--------

Find the the node (c) at which both the linked lists meet / collide.

Solution:

  1. Traverse both the lists and find their lengths 'a' and 'b' respectively.
  2. calculate the difference between both lengths: d = |a-b|
  3. Make two pointers PA and PB for each list.
  4. Move the pointer of the longer list 'd' steps.
  5. Then move both the pointers simultaneously until both the pointers become equal, which happens at the node 'c'.

No comments:

Post a Comment