Сторнирование связанного списка с циклом

Question

Как мы можем перевернуть связанный список, если у него есть цикл (т. Е. Если последний узел связан с узлом в середине)?

Что ж, я видел, что одно из решений здесь и здесь , чтобы обнаружить цикл в связанном списке, означает его обратное.Я сомневаюсь - как можно отменить связанный список, если вы не знаете, где он заканчивается.Как можно даже обратить связанный список, который имеет цикл?

Answer 1

Ну, во-первых, вам нужно определить, что означает «обратный» в этом контексте. Вероятно, что вам нужно сделать, это

(1) найти ссылку, которая делает его циклическим

(2) разорвать эту ссылку

(3) затем как-то перевернуть список.

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

в псевдокоде, вам нужен стек с операцией isIn

   stack:
     init()
     push(node)
     pop() returns node
     isIn(node) returns Boolean

и сделайте что-то вроде

 do
    get next node
    if node isIn stack
    then
       while stack not empty
           pop node
       break
    else
       push node in stack
    fi
 od

Answer 2

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

1->2->3->4->5-|
      ^       |
      |-------|                

Так что, если обычно список будет печататься: 12345345345, если вы продолжите обходить цикл, допустим, что перевернутый связанный список будет означать, что все стрелки повернули свое направление и наоборотон должен напечатать 54354312

Теперь вы можете сделать что-то вроде этого:

prev=head;
curr=head->next;
while !curr->visited && curr->next!=end 
    tmp=prev
    prev=curr
    curr=curr->next
    prev->next=tmp
    curr->visited=True

Это псевдокод, и они могут быть небольшими ошибками в логике, поэтому не копируйте дословно, но это один из основныхидея.