[Amazon]Flatten a Linked-List
You are given a singly link-list such that each node of this list is also a
head of another link list of the same type. So, suggest an algorithm to flatten the
linked-list in single level link-list.
struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;
};
head of another link list of the same type. So, suggest an algorithm to flatten the
linked-list in single level link-list.
struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;
};
Why we will create an array of size 2*h+1.it also invlolves finding the height of tree.
ReplyDeleteBetter approach may be->
Find the total no. of vertical lines this way ->
Use Inorder DFS to find the distance of leftmost node from root and distance of rightmost node from root
Total vertical lines= leftdistance + 1 + rightdistance
Now fill the array using same logic of +1,-1.
Time Complexity still remains - O(n)
//Please ignore above post
ReplyDeleteSolution to the current problem- >
Can't think of a better than O(n) solution
Use two pointers currentDown,which points to the down of current and nextNode, which points to next of current node.Move downwards to currentNode till end and then make it point to next of currentNode.
When currentDown and nextNode both points to NULL,we have reached end of list.
while(currentdown || nextnode )
{
while(currentDown)
{
current->next=currentDown;
current=current->next;
currentDown=currentDown->down;
}
current->next=nextNode;
current=current->next;
nextNode=current->next;
currentDown=current->down;
}
Time Complexity - O(n) Space Complexity - O(1)
@naveen your approach is correct..:)
ReplyDelete