430.扁平化多级双向链表

链接：430.扁平化多级双向链表
难度：Medium
标签：深度优先搜索、链表、双向链表
简介：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表，请你扁平化列表，使所有结点出现在单级双链表中。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：72ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：递归格式化每一层。

function flatten(head: Node | null): Node | null {
  if (head === null) return null;
  let p: Node | null = head;
  while (p) {
    format(p);
    p = p.next;
  }
  return head;
  function format(node: Node) {
    if (!node.child) return;
    const { next, child } = node;
    if (next) {
      next.prev = null;
      let prev: Node | null = null;
      let p: Node | null = child;
      while (p) {
        format(p);
        prev = p;
        p = p.next;
      }
      prev!.next = next;
      next.prev = prev;
    }
    node.child = null;
    node.next = child;
    child.prev = node;
  }
}

题解 2 - javascript

• 编辑时间：2021-09-24
• 执行用时：64ms
• 内存消耗：39.7MB
• 编程语言：javascript
• 解法介绍：递归格式化。

function flatten(head: Node | null): Node | null {
  if (head === null) return null;
  return format(head)[0];
  function format(node: Node): [Node, Node] {
    if (node.child === null && node.next === null) return [node, node];
    node.prev = null;
    let prev: Node = node;
    let p: Node | null = node;
    while (p) {
      const next = p.next;
      if (p.child) {
        const [first, last] = format(p.child);
        p.next = first;
        first.prev = p;
        last.next = next;
        if (next) next.prev = last;
        prev = last;
      } else {
        prev = p;
      }
      p.child = null;
      p = next;
    }
    return [node, prev];
  }
}