Сглаживание многоуровневого связного списка в Javascript - PullRequest
Новая
       93

Сглаживание многоуровневого связного списка в Javascript

0 голосов
/ 12 апреля 2020

Проблема: Выровнять многосвязный список (n строк и m столбцов), который отсортирован по вертикали и по горизонтали сверху.

При наличии связанного списка, в котором, помимо следующего указателя, каждый узел имеет дочерний указатель, который может указывать или не указывать на отдельный список. Эти дочерние списки могут иметь одного или нескольких собственных дочерних элементов и т. Д., Чтобы создать многоуровневую структуру данных, как показано на рисунке ниже. Вам дают голову первого уровня списка. Выровняйте список так, чтобы все узлы отображались в одноуровневом связанном списке. Вы должны сгладить список таким образом, чтобы все узлы первого уровня были первыми, затем узлы второго уровня и т. Д. 

5 -> 10 -> 19 -> 28
|    |     |     |
V    V     V     V
7    20    22    35
|          |     |
V          V     V
8          50    40
|                |
V                V
30               45

NOTE: this question was asked in an amazon interview 

// Javascript program for flattening a Linked List

/* Linked list */
class LinkedList {
  // constructor
  constructor() {
    this.head = null;
    this.size = 0;
  }
}

/* Linked list Node*/
class Node {
  // constructor
  constructor(data) {
    this.data = data;
    this.right = null;
    this.down = null;
  }
}

/* Utility function to insert a node at the beginning of the
       linked list */
addNode = function(head, data) {
  // creates a new node
  var new_node = new Node(data);
  // to store current head
  new_node.down = head;
  // assign head to new node
  head = new_node;

  this.size++;
  this.head = head;
  return head;
}


printList = function(head) {
  var curr = head;
  var str = "";
  while (curr != null) {
    str += curr.data + " ";
    curr = curr.down;
  }
  console.log(str);

}

// An utility function to merge two sorted linked lists
merge = function(a, b) {
  // if first linked list is empty then second
  // is the answer
  if (a == null) return b;

  // if second linked list is empty then first
  // is the result
  if (b == null) return a;

  // compare the data members of the two linked lists
  // and put the larger one in the result
  if (a.data < b.data) {
    var result = a;
    result.down = merge(a.down, b);
  } else {
    result = b;
    result.down = merge(a, b.down);
  }

  result.right = null;
  return result;
}


flatten = function(root) {
  // Base Cases
  if (root == null || root.right == null)
    return root;

  // recur for list on right
  root.right = flatten(root.right);

  // now merge
  root = merge(root, root.right);

  // return the root
  // it will be in turn merged with its left
  return root;
};



var L = new LinkedList();


/* Let us create the following linked list
    5 -> 10 -> 19 -> 28
    |    |     |     |
    V    V     V     V
    7    20    22    35
    |          |     |
    V          V     V
    8          50    40
    |                |
    V                V
    30               45
*/

L.head = addNode(L.head, 30);
L.head = addNode(L.head, 8);
L.head = addNode(L.head, 7);
L.head = addNode(L.head, 5);

L.head.right = addNode(L.head.right, 20);
L.head.right = addNode(L.head.right, 10);

L.head.right.right = addNode(L.head.right.right, 50);
L.head.right.right = addNode(L.head.right.right, 22);
L.head.right.right = addNode(L.head.right.right, 19);

L.head.right.right.right = addNode(L.head.right.right.right, 45);
L.head.right.right.right = addNode(L.head.right.right.right, 40);
L.head.right.right.right = addNode(L.head.right.right.right, 35);
L.head.right.right.right = addNode(L.head.right.right.right, 28);


// flatten the above linked list
L.head = flatten(L.head);
// print the flatten linked list
printList(L.head);

/* This code is contributed by Amit Yadav */
...