FlattenMultilevelLinkedList

/*
https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/
430. Flatten a Multilevel Doubly Linked List
Medium

1068

141

Add to List

Share
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:

After flattening the multilevel linked list it becomes:

*/

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        
        if(head==null) return head;
        
        Node curr=head;
        
        while(curr!=null){
            
            if(curr.child!=null) adjustChild(curr);
            
            curr=curr.next;
        }
        
        return head;
    }
    
    public void adjustChild(Node curr){
        
        Node next=curr.next;
        
        Node child=curr.child;
        
        curr.next=child;
        child.prev=curr;
        curr.child=null;
        
        while(child.next!=null){
            child=child.next;
        }
            
        child.next=next;
        next.prev=child;
    }
}