CareerCup

this can be done by trversing the linked list and check if child is not null then modify the pointers in list.

[nod1]<>[node2]<>[--]..............[--]
| | | |
list1 l ist 2 list 3.............list4

for each node just do following
node1->next=list1(head);
list1(head)->previous=node1;
list1(tails)->next=node2;
node2->previous=list1(tails);

this is code
cur=start;

while(cur=>next!=NULL)
{
temp=cur->next;
temp2=cur->child;
if(temp2)   //if child exist
{
temp3=temp2;
while(temp3->next!=NULL)
   temp3=temp->next;
//node u have found end of child list just change pointers
cur->next=temp2;
temp2->previous=cur;
temp3->next=temp1;
temp1->previous;

//
now increment current pointer for next node
cur=temp1;
}
else
cur=cur->next;  //if child was NULL just go ahead
}
}

for any clarification or bug please comment

I dint compile it. But logic is correct.

If a node has child
-> push the next element to stack checking whether the next is null or not.
-> move to the child after manipulating the prev and next pointers.
else
->move to next pointer if next is not null
->otherwise
->->check whether there is an element in the top of the stack. If present then pop and manipulate the prev and next pointers and assigned the the popped element for next iteration.
->->else break from the loop.

Hope this gonna work!

typedef struct node {
  int value ;
  struct node *prev ;
  struct node *next ;
  struct node *child ;
}node;

node* flattenTree (node* head) {
  node *cur = head ;
  stack <node*> s ;
  while ( cur != null ) {
    if ( hasChild (cur) ) {
      if ( cur->next != null ) 
        s.push (cur->next) ;
      node* child = cur->child ;
      cur->child = null ;
      cur->next = child ;
      child->prev = cur ;
      cur = child ;
    } else {
      if ( cur->next != null )
        cur = cur->next ;
      else if ( !s.empty() ) {
        node* popped = s.top() ;
        s.pop () ;
        cur->next = popped ;
        popped->left = cur ;
        cur = popped ;
      } else break ;
    }
  }
  return head ;
}

Kindly explain where is the child?

we create a blank link list. we make a recursive function say, makelist(*ptr). and pass the head of the list. if the child is not null of a given node we clall makelist(x->child) and then we add this node to new link list and then call makelist(x->next).

int flattern(struct dll *head, stuct dll *tail)
{
if(!head) return 0;
struct dll *temp;
for(temp = head; temp != tail; temp_node = temp->next) {

if (temp->data) {
tail->next = temp->data;
while(tail->next) tail = tail->next;
}
}
return 1;
}

void flatten(Node*& first, Node*& last) {
  vector<Node*> children;
  last = NULL;
  Node* curr = first;
  // Find all child lists and last element of this list
  while (curr != NULL) {
    if (curr->child) children.push_back(curr->child);
    curr->child = NULL;
    last = curr;
    curr = curr->next;
  }
  // Append child lists at the end
  for (int c = 0; c < children.size(); c++) {
    Node* child = children[c];
    Node* child_list_last;
    flatten(child, child_list_last);
    last->next = child;
    child->prev = last;
    last = child_list_last;
  }
}

Approach: This structure is similar to a tree. analogy: child => oldest son of the tree, next => current node's younger brother.

pseudo code:
function call: preOrderTraverse(pointer to first node i.e. head of LL)

void preOrderTraverse(curr)
{
    static pointer * previousNode
    if (curr != NULL)
    {
        if (previousNode != NULL)
        { 
            tie previousNode with curr node by manipulating prev and next ptrs of these nodes
        }
        else
        {
            head of resultant LL is = curr
        }
        previousNode = curr




preOrderTraverse(curr->child)
        preOrderTraverse(curr->next)
    }
}

I think there should not be any cycle! Because each child can refer to its same structure of the double linked list! As this is tree, there should not be any cycle!

It can be done using BFS.
Here is the code in C#:

public static void FlattenWORecursion(Node root)
            {
                if (root == null)
                {
                    throw new ArgumentNullException("root");
                }

                Node h = root, t = root;

                Queue<Node> q = new Queue<Node>();
                q.Enqueue(root);
                while (q.Count != 0)
                {
                    Node n = q.Dequeue();
                    if (n != null)
                    {
                        q.Enqueue(n.Left);
                        q.Enqueue(n.Right);
                        t.SetRight(n);
                        n.SetLeft(t);
                        t = n;
                    }     
                }

                root = h;
                t.SetRight(root);
            }

struct node
{
	node *previous;
	node *next;
	node *child;
	int value;
};
node *pt;
	node *last=tail;
	for(pt=head;pt!=last;pt=pt->next)
	{
		if(pt->child!=NULL)
		{
			traverse(pt->child,tail);
			child=NULL;
		}
	}
	if(last->child!=NULL)
	{
		traverse(last->child,tail);
		child=NULL;
	}
void traverse(node *pt,node *tail)
{
	node *pt1;
	for(pt1=pt;pt1!=NULL;pt=pt->next)
	{
		tail->next=pt1;
		pt1->previous=tail;
		tail=pt1;
		if(pt1->child!=NULL)
		{
			traverse(pt1->child,tail);
			pt1->child=NULL;
		}
	}
}

// Java code for flatten, based on pre-order traversal.  
// When we visit a node, we append that node to a new linked list.
// No new nodes are created, so we must be careful not to remove 
// pointers that might be needed in the pre-order traversal.
// Pass array of size 1 to simulate pass-by-reference in Java.
void preOrderFlatten(Node n, Node[] new)
{
   //  Loop over nodes of a list.
   while (n != null)
   {
      //  Visit node by appending to growing new list.
      if (new[0] != null)
      {
         new[0].next = n;
         n.prev = new[0];
      }
      //  Preserve the tail of the growing list.
      new[0] = n;

      //  Recursion.
      preOrderFlatten(n.child, new);

      //  Continue loop.
      n = n.next;
   }
}

Refer to:
Programming Interviews Exposed/Chapter 4/List Flattening

start from head, if child is existed make a link to the child, and trace until the end of child's chain and link to the next node of the current pointer. move to the next node until the end.

Node * FlattenNodes(Node *head)
{
	Node * p = head;
	while (p!=NULL)
	{
		if(p->child!=NULL)
		{
			Node *ch=p->child;
			while(ch->next!=NULL)
				ch=ch->next;
			p->child->last=p;
			ch->next=p->next;
			if(p->next!=NULL)
				p->next->last=ch;
			p->next=p->child;
			p->child=NULL;
		}
		p=p->next;
	}
	return head;
}