Linked List - Question 8 Merge Multi-Level Doubly Linked List (Medium)

Question

Given a doubly linked list, list nodes also have a child property that can point to a separate doubly linked list. These child lists can also have one or more child doubly linked lists of their own, and so on.
Return the list as a single level flattened doubly linked list.

Verify the constraints

1. Can a doubly linked list have multiple child list nodes? - Yes, every list node can have multiple levels of children
2. What do we do with child properties after flattening? - Jest set the child property value to null

Write out some test cases

1. 1 - 2 - 3 - 4 - 5 - 6 (2 -7 - 8 - 9) (8 - 10 - 11) (5 - 12 - 13) // 1 - 2 - 7 - 8 - 10 - 11 - 9 - 3 - 4 - 5 - 12 - 13 - 6

Figure out a solution without code

Write out our solution in code

Solution 1

function flattenMultiLevelDoublyLinkedList(head){
	let currentNode = head;
	let spinPointNode = [];
	let spinPointNextNode = [];
	while(currentNode){
		if(currentNode.child !== null){
	           spinPointNode.push(currentNode); //child로 빠지는 시점의 node를 spinPointNode에 저장
	            if(currentNode.next !== null){
	                spinPointNextNode.push(currentNode.next); //child로 빠지는 시점의 node의 다음 노드를 spinPointNextNode에 저장
	            }
		    currentNode.next = currentNode.child; //child로 빠질 때 그 다음 노드(next node)와의 연결 끊고 child를 next노드로 만들기
	            currentNode.child.prev = currentNode; //child의 prev노드를 currentNode로 가리키게 만들기
	            let child = currentNode.child; //연결 끊기 전에 child를 따로 저장
	            currentNode.child = null; //child 노드 없애기
	            currentNode = child; //childNode로 이동
	        }else{
	            if(currentNode.next === null){ //노드의 끝 도착
	                if(spinPointNextNode.length === 0){ //만약 spinPointNextNode 배열에서 뽑을 노드가 더 이상 없으면 break해서 빠져나오기
	                    break;
	                }
	                const nextNode = spinPointNextNode.pop(); //그 다음 노드를 저장해둔 spinPointNextNode 배열에서 뽑기
	                currentNode.next = nextNode; //현재 노드의 다음 노드를 spinPointNextNode 배열에서 뽑은 노드와 연결하기
	                currentNode.next.prev = currentNode; //다음 노드의 prev노드를 현재 노드를 가리키게 만들기
            }
            currentNode = currentNode.next; //다음 노드로 이동
        }
    }
    return head;
}

Solution 2

class ListNode {
  constructor(val, next = null, prev = null, child = null) {
    this.val = val;
    this.next = next;
    this.prev = prev;
    this.child = child;
  }
}

// ---- Generate our linked list ----
const nodes = [1, [2, 7, [8, 10, 11], 9], 3, 4, [5, 12, 13], 6]

const buildMultiLevel = function(nodes) {
  const head = new ListNode(nodes[0]);
  let currentNode = head;

  for(let i = 1; i < nodes.length; i++) {
    const val = nodes[i];
    let nextNode;

    if(Array.isArray(val)) {
      nextNode = buildMultiLevel(val);
      currentNode.child = nextNode;
      continue;
    }

    nextNode = new ListNode(val);
    currentNode.next = nextNode;
    nextNode.prev = currentNode;
    currentNode = nextNode;
  }
  
  return head;
}

let multiLinkedList = buildMultiLevel(nodes);

// ---- Generate our linked list ----

const printListMulti = head => {
  if(!head) {
    return;
  }

  console.log(head.val)

  if(head.child) {
    printListMulti(head.child);
  }

  printListMulti(head.next);
}

const printList = head => {
  if(!head) {
    return;
  }

  console.log(head.val);
  
  printList(head.next);
}

// --------- Our solution -----------

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

  let currentNode = head;
  while (currentNode !== null) {
    if (currentNode.child === null) {
      currentNode = currentNode.next;
    } else {
      let tail = currentNode.child;
      while (tail.next !== null) {
        tail = tail.next;
      }

      tail.next = currentNode.next;
      if (tail.next !== null) {
        tail.next.prev = tail;
      }

      currentNode.next = currentNode.child;
      currentNode.next.prev = currentNode;
      currentNode.child = null;
    }
  }

  return head;
};

printListMulti(multiLinkedList);
console.log('after flatten');
printList(flatten(multiLinkedList));

Analyze Space and Time Complexity

• Solution 1
  • Time Complexity: O(N)
  • Space Complexity: O(N)
• Solution 2
  • Time Complexity: O(N)
  • Space Complexity: O(1)

Developing References

Developing Report

2025-01-24 - Linked List - Question 8 Merge Multi-Level Doubly Linked List (Medium) Report
2025-01-24 - Developing Daily Report
2025-01-4th - Developing Weekly Report