루프가있는 연결된 목록 반전

Question

루프가있는 경우 (예 : 마지막 노드가 중간에있는 노드에 연결되어있는 경우) 링크 된 목록을 되돌릴 수 있습니까?

글쎄, 나는 solutions in here과 here 중 하나가 링크 된 목록의 루프를 감지하는 것이 그것을 뒤집어 쓴다는 것을 알았다. 나의 의심은 - 그것이 어디에서 끝나는 지 모른다면 어떻게 링크 된 목록을 되돌릴 수 있습니다. 어떻게하면 루프가있는 연결된 목록을 역전시킬 수 있습니까?

Answer 1

글쎄, 먼저, 당신은 "역전"이 의미하는 바를 정의 할 필요가있을 것입니다. 아마, 당신이해야 할 것은

(1)가 순환

(2) 링크를 깰 수있는 링크를 찾을 수 있습니다

(3) 어떻게 든 목록을 역.

효율적으로 수행하는 것이 순환을 식별하는 효율적인 방법을 찾는 것입니다. 그러나 노드가 이미 존재하는지 여부를 알려주는 작업이있는 스택을 가정하면 이미 본 노드에 대한 링크를 줄 때까지 노드를 스택으로 밀어 넣을 수 있습니다. 그런 다음 스택을 팝업하고 voila 역순으로 목록이 있습니다.

은 의사에, 당신은 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

같은 난 당신이 그것과 연결리스트를 반대하는 의미를 정의 할 필요가 첫번째 생각 하는가 고리. 당신의이 반전 된 연결리스트는 모든 화살표가 방향을 반전하고 반대로 그것을해야 의미 가정 해 봅시다주기를 가로 지르는 유지하는 경우 12,345,345,345 :

그래서 만약

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

일반적으로 목록 인쇄 것 :의 당신이 링크 된 목록을 가정 해 봅시다

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 

이 의사 코드와 논리에 자신이 될 수있는 작은 오류가 너무 그대로 복사하지 마십시오하지만 하나의 기본적인 생각이다.