Popular Posts

Sunday, July 31, 2011

Problem:
There are 2 link lists merging at some node. Find the node, where these 2 lists merge.


Solution:
             

  1. Point both the heads with temp1 and temp2 pointers.
  2. Move both pointers one step at a time.
  3. Repeat step 2 until temp1 or temp2 reaches the last node.
  4. Make a pointer P1 to point the head of longest list and pointer P2 to point the head of another list.
  5. Move the temp pointer of longest list and another pointer from its list head one position at a time until temp reaches the last node.
  6. Now we have two pointers with equal numbers of nodes.
  7. move two pointers one at a time until they both meet.
  8. return the merge node.

Complexity: O(m+n)
Code:



No comments:

Post a Comment