/**
 * // Definition for a Node.
 * function Node(val,prev,next,child) {
 *    this.val = val;
 *    this.prev = prev;
 *    this.next = next;
 *    this.child = child;
 * };
 */

/**
 * @param {Node} head
 * @return {Node}
 */
var flatten = function (head) {
  function flattener(node) {
    // null Exception 처리
    if (node === null) return;
    // node.child 가 있을 때
    else if (node.child) {
      // 1. node.next 를 저장해둔다.
      const holdingPointer = node.next;

      // 2. node 와 node.child 를 next / prev 관계로 수정한다.
      node.next = node.child;
      node.child.prev = node;

      // 3. node.child 로 flattener 함수를 재귀해 해당 level 의 tail 을 return 시켜 저장한다.
      const tailOfChild = flattener(node.child);

      // 4.  1 번에서 저장한 holdingPointer 가 null 이 아닐경우
      //     tail 과 holdingPointer 를 next / prev 관계로 연결한다.
      if (holdingPointer) {
        tailOfChild.next = holdingPointer;
        holdingPointer.prev = tailOfChild;
      }

      // 5. traverse 가 끝난 child 를 null 로 저장해 참조를 끊어준다.
      node.child = null;

      // 6. 4번에서 연결된 holdingPointer 부터 다시 traverse 시작한다.
      return flattener(holdingPointer);
    } else if (node.next) {
      return flattener(node.next);
    } else if (!node.next) {
      // next 가 없으면 tail 이므로 return 시킨다.
      return node;
    }
  }

  flattener(head);

  return head;
};

var flatten = function (head) {
  if (!head) return null;

  // while 문으로 처리할 traverse 의 시작 node 가 될 dummyHead 선언
  let dummyHead = new Node(0, null, head, null);

  // traverse 중 next node 를 저장하고 꺼내어 current node 로 사용하기 위해 stack 선언
  // stack 의 FIFO 의 특성상 상위 level 의 traverse 를 그대로 중지시키고
  // 그 node 위에 child node 를 push 하고 pop 하며 하위 level 의 traverse 를 처리할 수 있다.
  // 하위 level 의 traverse 가 끝나면 자연스럽게 stack 의 다음 node 부터 시작하여 부모 level 을
  // 이어서 traverse 할 수 있다.
  let stack = [head];
  let current = dummyHead;
  let prev = null;

  while (stack.length != 0) {
    current = stack.pop();

    // 순서대로 traverse 하면 prev (이전) node 가 저장되어 있을 경우에만
    // 해당 node 와 prev / next 연결 할 수 있다.
    if (prev) {
      current.prev = prev;
      prev.next = current;
    }

    if (current.next != null) stack.push(current.next);
    if (current.child != null) {
      // has a child
      stack.push(current.child);
      current.child = null; // remove child reference
    }

    prev = current;
  }

  return dummyHead.next;
};