Как повернуть столбец в сетке двусвязного списка

Question

Если бы у меня была сетка из двойных связанных списков, т.е. каждый узел имеет 4 указателя, влево, вправо вверх и вниз.Как бы я повернуть столбец т.е.в сетке

    A B C D


    1 2 3 4


    E F G H

узел D имеет следующие указатели: left = C right = A up = H и down = 4, как мне сделать сетку похожей:

    A B C 4


    1 2 3 H


    E F G D

после вызова функции rotate (3,2), где первый аргумент - это строка, а второй - количество слотов для поворота вниз.

Примечание. Я работаю в C ++

Answer 1

После долгих раздумий я придумал способ, который не требует дополнительной памяти:

• Возьмите узел N в данном столбце вместе с его левыми и правыми соседями L и R.
• Следуйте указателю N->down k раз, присвойте результат N.
• Пусть M = N, выполняйте следующие действия до тех пор, пока M = N снова:
  • Точка *От 1011 * до M и M->right до L
  • Точка R->left до M и M->right до R
  • Возьмите указатель вниз для L, M и R.

В коде это будет выглядеть так:

void rotate_down(Node * N, unsigned int k) {
  Node * L = N->left;
  Node * R = N->right;
  while (k-- > 0) N = N->down;
  Node * M = N;
  do {
    L->right = M; M->left = L;
    R->left = M; M->right = R;
    L = L->down; M = M->down; R = R->down;
  } while (M != N);
}

Для дополнительного кредита сделайте эту функцию общей в направлении движения с помощью параметра шаблона.

Answer 2

Это звучит как один из тех хитрых вопросов в интервью по кодированию.Где вы думаете, вы должны управлять всеми этими сложными отношениями указателя.Но более простое решение - просто переместить значения между узлами в списке и оставить указатели между узлами как есть.Подсказка в вашем собственном описании проблемы (где вы сказали «похоже» ).

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

// for each item in the column, copy its value to the item above it
void RotateColumn(Node* firstnode)
{
    Node* current = firstnode;
    Node* next = current->down;
    char firstvalue = current->value;
    while (next != firstnode)
    {
       current->value = next->value;
       current = next;
       next = next->down;
    }
    current->value = firstvalue;
}