Problem:
There are 2 link lists merging at some node. Find the node, where these 2 lists merge.
Solution:
             
Complexity: O(m+n)
Code:
There are 2 link lists merging at some node. Find the node, where these 2 lists merge.
Solution:
- Point both the heads with temp1 and temp2 pointers.
 - Move both pointers one step at a time.
 - Repeat step 2 until temp1 or temp2 reaches the last node.
 - Make a pointer P1 to point the head of longest list and pointer P2 to point the head of another list.
 - 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.
 - Now we have two pointers with equal numbers of nodes.
 - move two pointers one at a time until they both meet.
 - return the merge node.
 
Complexity: O(m+n)
Code:

No comments:
Post a Comment