Можно ли перевернуть связанный список, содержащий цикл?

Question

Я смотрю на некоторые вопросы интервью, и один из них просит перевернуть связанный список, содержащий цикл. Предположим, у меня был связанный список, подобный следующему:

          F <- E
          |    /\
          V    |
A -> B -> C -> D 

Тогда обратный список создаст следующее:

          F -> E
         /\    |
          |    V
A <- B <- C <- D

Проблема в том, что существует конфликт между узлами C, на которые должен указывать. Так мы бы просто устранили связь между C и F?

Answer 1

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

Если связанный список не содержит цикл, то эта частичная функция является инъективной (один к одному), что означает, что никакие два узла не отображаются в один и тот же преемник. Инъективные функции действительно могут быть инвертированы, поэтому вы можете перевернуть обычный связанный список. Однако, если список содержит цикл, то есть два узла с одним и тем же преемником, поэтому функция не является инъективной и, следовательно, не имеет обратного. Поэтому нет, вы не можете перевернуть связанный список и ожидать получения другого связанного списка, если в списке есть цикл.

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

Answer 2

Исходный список будет AB CDEF CDEF CDEF ... Чтобы обратить вспять, вам понадобится связанный список, который генерирует FEDC бесконечное число раз, за ​​которым следует BA, поэтому я бы сказал, нет, нет способа построитьсвязанный список, который будет генерировать эту последовательность.