Выравнивание многоуровневого связанного списка

#algorithm #linked-list #queue #pseudocode

#алгоритм #связанный список #очередь #псевдокод

Вопрос:

Вопрос

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

Цель.

Нам нужно выровнять список таким образом, чтобы все узлы первого уровня были первыми, затем узлы второго уровня и так далее.

введите описание изображения здесь

Приведенный выше список должен быть преобразован в

10->5->12->7->11->4->20->13->17->6->2->16->9->8->3->19->15

Мой подход:

 1) Create an empty queue
2) while(Queue is not empty AND head.next!=null AND head.child!=null)
     2a) while(head!=null)
           if(head.child!=null)
               Enqueue(head.child)
           newList = head;
           head = head.next;
           newList = newList.next;
     2b)head = deQ();

Правильный ли этот подход?

1. Это псевдокод, но все же не Queue is not empty эквивалентно head.next!=null AND head.child!=null . Кроме этого, ваш подход кажется мне правильным.

2. Существует решение с двумя пальцами, которое работает на месте без дополнительной структуры данных. (Хорошо, для этого нужны два пальца, но это просто указатели на узлы.) Я предполагаю, что это домашнее задание, и вы бы предпочли разобраться в нем самостоятельно, верно?

3. @rici это не домашнее задание. Также не могли бы вы или @aa333 указать условие завершения в строке 2) из while ?

4. @Dubby: Ок, добавлено решение. Я уверен, что я предоставил этот же алгоритм для BFS в другом месте на SO. Существует также версия с глубиной в два пальца, в которой дочерние ссылки используются для поддержки стека рекурсии; возможно, вам понравится разбираться в этом.

Ответ №1:

Вот простой обход шириной в два пальца (порядок уровней), который выполняет выравнивание на месте. (Любители эффективности могут захотеть изменить циклы, потому что некоторые тесты выполняются дважды, но это вряд ли имеет значение.) Основная идея заключается в том, что существует неявная очередь, состоящая из узлов между finger2 и finger1 . finger1 перемещается вперед по уровню, и каждый раз, когда он достигает узла без правого родственного узла, «очередь» продвигается вперед, перемещаясь finger2 вправо, пока не найдет дочерний элемент, который затем добавляется, finger1 чтобы finger1 он мог продолжать двигаться вправо.

 finger1 = finger2 = head;
while finger2 is not Null:
  while finger1.next is not Null: finger1 = finger1.next
  while finger2 is not Null and finger2.child is Null: finger2 = finger2.next
  if finger2 is not Null:
    finger1.next = finger2.child
    finger2.child = Null

Ответ №2:

Простое решение на основе стека, которое проходит до следующего конца, затем присоединяет дочерние элементы из стека.

 node *flatten(node *head) {
    stack<node *> s;
    node *curr = root;
    while (1) {
        if (curr->next) { // keep moving in current streak
            if (curr->child)
                s.push(curr);
            curr = curr->next;
        }
        else { // attach child branch and continue from there
            if (s.empty())
                return head;
            curr->next = s.top()->next;
            s.top()->next = NULL;
            s.pop();
            curr = curr->next;
        }
    }
}