[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;
};
 

Comments

  1. Why we will create an array of size 2*h+1.it also invlolves finding the height of tree.
    Better 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)

    ReplyDelete
  2. //Please ignore above post
    Solution 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)

    ReplyDelete
  3. @naveen your approach is correct..:)

    ReplyDelete

Post a Comment

Popular posts from this blog