[LeetCode] 430. Flatten a Multilevel Doubly Linked List, Medium

• child라는 필드를 추가적으로 가지는 멀티 레벨 이중 연결 리스트가 주어질 때, 모든 child를 없애 단일 이중 연결 리스트로 재구성 하라.

2. 해결

/**
 * Definition for _Node.
 * 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 recursive(head: _Node, curr: _Node | null) {
    let p1 = head;
    
    while(p1) {
        if(p1.child) { // 자식이 있으면 재귀.
            const lastChildNode = recursive(p1.child, p1); // 아래를 통해 자식 리스트의 마지막 노드 반환.
            p1.next = p1.child  // 현재 자식 노드를 다음 노드로 연결.
            p1.next.prev = p1; // 자식 노드였던 노드의 prev를 연결.
            p1.child = null; // 자식은 null로 변경.
            p1 = lastChildNode; // 위에서 받은 마지막 노드로 포인터로 연결.
            continue;
        } else if(!p1.next && curr) { // 최하위 레벨의 마지막 노드인 경우,
            p1.next = curr.next; // 부모 노드의 다음 노드와 연결.
            if(curr.next) // 부모 노드의 다음 노드가 있으면,
            curr.next.prev = p1; // 해당 노드의 prev도 연결.
            return p1;
        }        
        p1 = p1.next;
    }
}

function flatten(head: _Node | null): _Node | null {
    recursive(head, null);
    
    
    return head;
};

• 비슷한 형태로 연산이 반복된다면 재귀를 활용하자. 
• 자식 노드의 첫 번째, 마지막 노드와 자식 노드가 있는 노드에 대한 연산이 키 포인트이다.