扁平化多级双向链表

/*
 * Problem: Flatten a multilevel doubly linked list using Java Streams.
 * 
 * Approach:
 * 1. Convert the linked list into a list of nodes, including child nodes.
 * 2. Flatten the list of nodes into a single list using a stream.
 * 3. Reconstruct the linked list from the flattened list.
 */

import java.util.*;
import java.util.stream.*;

class Node {
    int val;
    Node next;
    Node prev;
    Node child;

    Node(int val) {
        this.val = val;
    }
}

public class Solution {
    public Node flatten(Node head) {
        if (head == null) return null;

        // Create a list of all nodes, including child nodes
        List<Node> nodes = new ArrayList<>();
        flattenList(head, nodes);

        // Flatten the list using streams and set the child pointers to null
        List<Node> flattenedList = nodes.stream()
            .flatMap(n -> n.child == null ? Stream.of(n) : Stream.concat(Stream.of(n), flattenChild(n.child).stream()))
            .peek(n -> n.child = null)
            .collect(Collectors.toList());

        // Reconstruct the linked list
        Node dummy = new Node(0);
        Node curr = dummy;
        for (Node node : flattenedList) {
            curr.next = node;
            node.prev = curr;
            curr = curr.next;
        }
        dummy.next.prev = null;
        return dummy.next;
    }

    private void flattenList(Node head, List<Node> nodes) {
        Node curr = head;
        while (curr != null) {
            nodes.add(curr);
            if (curr.child != null) flattenList(curr.child, nodes);
            curr = curr.next;
        }
    }

    private List<Node> flattenChild(Node child) {
        List<Node> childList = new ArrayList<>();
        flattenList(child, childList);
        return childList;
    }
}