### [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