Java | Recursion | 0 ms | Time: O(n) | Space: O(1)
Intuition\nWe iterate the list untill we reach a node which has child node, when we reach it, we will call the function again to flatten the child too.\nAnd the
# Intuition\nWe iterate the list untill we reach a node which has child node, when we reach it, we will call the function again to flatten the child too.\nAnd the function will return the last node of the child as we need to connnect it with next node of curent node. The process continues untill we reach end of the list.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Create a recursive function that flattens linkedlist and returns the last node of linkedList\n2. Inside function iterate over the curr node, when you reach a node which has child, call the function again\n3. Called function returns child node\'s last node, put it before current node\'s next node and after curr node.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/*\n// Definition for a Node.\nclass Node {\n    public int val;\n    public Node prev;\n    public Node next;\n    public Node child;\n};\n*/\n\nclass Solution {\n    public Node flatten(Node head) {\n        flat(head);\n        return head;\n    }\n    \n    public Node flat(Node head){\n        Node curr = head;\n        Node last = head;\n        while(curr!=null){\n            if(curr.child!=null){\n                //if we encounter child we will try to flatten that child and return its tail\n                Node midTail = flat(curr.child);\n\n                //if current node next is not null we need to connect it with curr next\n                Node next = curr.next;\n                if(next!=null){\n                    midTail.next = next;\n                    next.prev = midTail;   \n                }\n\n                //there we are connecting mid node\'s first node with curr node next pointer\n                curr.next = curr.child;\n                curr.child.prev = curr;\n\n                //we make sure all child nodes should be null;\n                curr.child = null;\n\n                //there, we are giving curr pointer to midTail which is the end of child linked list\n                curr = midTail;\n            }\n            //we used last pointer to get the last node of child\n            last = curr;\n            curr = curr.next;\n        }\n        return last;\n    }\n}\n```\n# **Please, upvote if you liked it**
['Java']