algoadvance

Clarifying Questions:

  1. What does each node of the list contain? Each node contains an integer value, a next pointer to the next node, a prev pointer to the previous node, and a child pointer to a potentially nested doubly linked list.

  2. What is the expected output? The output should be a singly list where all of the nodes, including those in nested levels, are flattened such that:
    • Each ‘child’ node appears immediately after its parent node and before the parent’s next node.
    • All child pointers should be removed.
  3. Are there any constraints?
    • If the input list is null, return null.
    • The number of nodes in the list is in the range [0, 1000].
    • Node values are integers.

Strategy:

  1. Iterate through the main list:
    • For each node, if it has a child pointer, we’ll need to flatten that part first.
    • Use a stack to keep track of the next nodes so that after flattening the child nodes, we can continue with the stored next nodes.
  2. Process child nodes:
    • If the node has a child, append the child list between the current node and the next.
    • Store the next node (if any) in a stack before diving into the child list.
  3. Iterate through the child list and continue until the end.
  4. Connect the tail of the flattened child list to the stored next node (if any).

Time Complexity:

The time complexity of this approach is (O(n)), where (n) is the total number of nodes in the list including all depths. This is because we are processing each node exactly once.

Code:

Below is a Python implementation of the solution:

# Node definition
class Node:
    def __init__(self, val: int, prev: 'Node' = None, next: 'Node' = None, child: 'Node' = None):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child

def flatten(head: 'Node') -> 'Node':
    if not head:
        return head
    
    # Create a pseudo head that allows to deal with edge cases easily
    pseudo_head = Node(0, None, head, None)
    prev = pseudo_head
    
    stack = []
    stack.append(head)
    
    while stack:
        curr = stack.pop()
        
        prev.next = curr
        curr.prev = prev
        
        # If we find a next node, add it to the stack
        if curr.next:
            stack.append(curr.next)
        
        # If we find a child node, add it to the stack
        if curr.child:
            stack.append(curr.child)
            curr.child = None  # Don't forget to remove the child reference
        
        prev = curr
    
    # Detach the pseudo head
    pseudo_head.next.prev = None
    return pseudo_head.next

Explanation:

  1. Pseudo Head - We create a dummy node pseudo_head to simplify handling edge cases (like empty list or single node list).
  2. Stack - Use a stack to manage nodes to be processed, mimic Depth-First Search (DFS).
  3. Iterate & Flatten - Adjust next and prev pointers while preserving child nodes into the flattened list.
  4. Remove Child Pointer - As each child is processed, its pointer is removed.

This approach ensures that all nodes are visited precisely once, making it efficient with (O(n)) time complexity.

Try our interview co-pilot at AlgoAdvance.com