> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/01-13-2022-430.md).

# 01/13/2022 430

method DFS recursion

This double linkedlist can be treated as a binary tree. Node child is the left subtree. Node next is the right subtree. If we combine the head + child + next, then we can get the result we want. So define a traverse method that returns the tail node of the flatten linkedlist. First we get the tail of the traverse(curr, curr.child), set curr.child = null, then recursively call the traverse(tail. curr.next)

Time O(N) Space O(n)

![](/files/CWEuFTVVcIYeNGsoTp3c)

```
class Solution { 
public Node flatten(Node head) { 
    if(head == null) return head; 
    Node dummy = new Node(0, null, head, null); 
    flatten_traverse(dummy,head); // dummy to ensure the prev pointer is never none dummy.next.prev = null; 
    return dummy.next;
}

private Node flatten_traverse(Node pre, Node curr){// return the tail of the flatten list;
    if(curr == null) return pre;
    
    curr.prev = pre;
    pre.next = curr;
    
    Node nextTemp = curr.next;
    
    Node tail = flatten_traverse(curr, curr.child);
    curr.child = null;
    
    return flatten_traverse(tail, nextTemp);   
    
}
```

}

method 2: using stack iteration

![](/files/MC2z9Y76mAPY0rcTIQRc)

public Node flatten(Node head) { Stack stack = new Stack<>(); if(head == null) return head;

```
    Node dummy = new Node(0,null, head,null);
    Node curr,prev = dummy;
    
    stack.push(head);
    
    while(!stack.isEmpty()){
        curr = stack.pop(); 
        prev.next = curr;
        curr.prev = prev;
        
        if(curr.next != null){
            stack.push(curr.next);
        }
        if(curr.child != null){
            stack.push(curr.child);
            curr.child = null;
        }
        
        prev = curr;
    
    }
    dummy.next.prev = null;
    return head;
    
```

```
public Node flatten(Node head) {
        if(head==null) return head;
        Node curr = head;
        
        while(curr!=null){
            if(curr.child!=null){
                Node down =  curr.child;
                while(down.next!=null) down = down.next;
                Node temp = curr.next;
                curr.next = curr.child;
                curr.child.prev = curr;
                curr.child= null;
                down.next = temp;
                if(temp!=null) temp.prev = down;
            }
            curr = curr.next;
        }
        return head;
    }
```