🔥

100日アルゴリズム[14日目・双方向リスト]

2024/04/10に公開

問題

回答


//  class Node {
//      val: number
//      prev: Node | null
//      next: Node | null
//      child: Node | null
//      constructor(val?: number, prev? : Node, next? : Node, child? : Node) {
//          this.val = (val===undefined ? 0 : val);
//          this.prev = (prev===undefined ? null : prev);
//          this.next = (next===undefined ? null : next);
//          this.child = (child===undefined ? null : child);
//      }
//  }
 

function flatten(head: Node | null): Node | null {
    if(!head) return null
    const dummy:Node = new Node(0, null, head)
     let stack: Node[] = [head];
    let prev: Node = dummy;

    while (stack.length) {
        let curr: Node | undefined = stack.pop();
        if (curr) {
            if (curr.next) stack.push(curr.next);
            if (curr.child) {
                stack.push(curr.child);
                curr.child = null;
            }
            prev.next = curr;
            curr.prev = prev;
            prev = curr;
        }
    }

    dummy.next!.prev = null;
    return dummy.next;
};

双方向リストとは

片方向リストでは、nextの値に次のノードの参照を保存しています。双方向リストでは、nextの他にprevにもノードの参照を保存します。それにより、双方向リストでは前のnodeから次のnodeの線形探索ができるだけでなく、n番目のnodeからn-1番目のnodeを逆検索することができます。

問題

回答

双方向リストとは

Discussion