Java Easy to Understand Solution with Explanation || 100% beats
Intuition\n> We can solve this easily using an iterative approach. When there is a child node, we need to point that child as the next node. For the end of that
# Intuition\n> We can solve this easily using an iterative approach. When there is a child node, we need to point that child as the next node. For the end of that child\'s sublist, we need to connect it to the next node of the main list.\n\n# Approach\n\n\n### Function Signature\n```java\npublic Node flatten(Node head) {\n```\nThe function `flatten` takes the head node of a multilevel doubly linked list and returns the head of the flattened list.\n\n### Initialization\n```java\nfor (Node curr = head; curr != null; curr = curr.next)\n```\n- We use a `for` loop to iterate through the nodes of the list using a pointer `curr`.\n- The loop continues until `curr` becomes `null`, indicating the end of the list.\n\n### Checking for Child Nodes\n```java\nif (curr.child != null) {\n```\n- Within the loop, we check if the current node (`curr`) has a `child` node.\n- If it does, we proceed to flatten the `child` list into the main list.\n\n### Storing the Next Node\n```java\nNode cachedNext = curr.next;\n```\n- We store the next node (`curr.next`) in a temporary variable `cachedNext` because we will temporarily disrupt this link to insert the child list.\n\n### Linking Child to the Main List\n```java\ncurr.next = curr.child;\ncurr.child.prev = curr;\ncurr.child = null;\n```\n- We make the `child` node the next node of the current node (`curr.next = curr.child`).\n- We set the `prev` pointer of the `child` node to the current node (`curr.child.prev = curr`).\n- We nullify the `child` pointer of the current node (`curr.child = null`).\n\n### Finding the Tail of the Child List\n```java\nNode tail = curr.next;\n\nwhile (tail.next != null) {\n    tail = tail.next;\n}\n```\n- We initialize a pointer `tail` to the start of the child list (`curr.next`).\n- We then traverse to the end of the child list to find its tail.\n\n### Linking the Tail of the Child List to the Cached Next Node\n```java\ntail.next = cachedNext;\n\nif (cachedNext != null)\n    cachedNext.prev = tail;\n```\n- We connect the tail of the child list to the `cachedNext` node.\n- If `cachedNext` is not `null`, we set its `prev` pointer to the tail of the child list.\n\n### Return the Flattened List\n```java\nreturn head;\n```\n- Finally, we return the head of the modified list, which is now flattened.\n\n### Example Walkthrough\n\nConsider a multilevel doubly linked list like this:\n\n```\n1 - 2 - 3\n    |\n    4 - 5\n```\n\n1. We start with `curr` at node 1.\n2. Move to node 2 (since node 1 has no child).\n3. Node 2 has a child (node 4). We:\n   - Cache `curr.next` (node 3).\n   - Set `curr.next` to `curr.child` (node 4).\n   - Nullify `curr.child`.\n4. Traverse the child list to its tail (node 5).\n5. Connect the tail (node 5) to the cached next node (node 3).\n6. Move `curr` to the next node and continue until the end of the list.\n\nThe final flattened list:\n\n```\n1 - 2 - 4 - 5 - 3\n```\n\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```\nclass Solution {\n  public Node flatten(Node head) {\n    for (Node curr = head; curr != null; curr = curr.next)\n            if (curr.child != null) {\n\n                Node cachedNext = curr.next;\n                curr.next = curr.child;\n                curr.child.prev = curr;\n                curr.child = null;\n                Node tail = curr.next;\n\n                while (tail.next != null) {\n                    tail = tail.next;\n                }\n\n                tail.next = cachedNext;\n\n                if (cachedNext != null)\n                    cachedNext.prev = tail;\n            }\n\n        return head;\n  }\n}\n```\n\n\n![image.png](https://assets.leetcode.com/users/images/6ebcff95-9f9b-411a-8b8a-15ff053f540c_1717056945.5111413.png)\n
['Linked List', 'Doubly-Linked List', 'Java']