Как перевернуть связанный список?

Question

Node reverse(Node head) { 
    Node previous = null; 
    Node current = head; 
    Node forward; 

    while (current != null) { 
     forward = current.next; 
     current.next = previous; 
     previous = current; 
     current = forward; 
    } 

    return previous; 
} 

Как именно он меняет направление? Я понимаю, что он сначала устанавливает второй узел на forward. Затем он говорит, что current.next равен null узел previous. Затем он говорит, что previous сейчас current. Наконец current становится forward?

Я, похоже, не понимаю этого и как его реверсирование. Может кто-нибудь объяснить, как это работает?

Answer 1

Вы изменяете список итеративно и всегда имеете правильный список в интервале [head, previous] (так что текущий - это первый узел, у которого его ссылка установлена ​​неправильно). На каждом шаге вы делаете следующее:

• Вы помните следующий узел тока, так что вы можете продолжить с его
• Вы можете установить ссылку тока, указывающий на предыдущий, что правильное направление, если вам думать об этом
• Вы можете изменить предыдущим быть текущими, потому что теперь ток также имеет свою ссылку установлена ​​правильно
• Вы меняете первый узел, который не Хэ~d его связи установлен правильно, чтобы быть один remebered на первом этапе

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

Answer 2

Код просто просматривает список и инвертирует ссылки до тех пор, пока не достигнет предыдущего хвоста, который он возвращает как новую голову.

До:

Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null 

После:

null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head) 

Answer 3

Answer 4

public Node getLastNode() 
{ 
    if(next != null) 
     return next.getLastNode(); 
    else 
     return this; 
} 

public Node reverse(Node source) 
{ 
    Node reversed = source.getLastNode(); 
    Node cursor = source; 

    while(cursor != reversed) 
    { 
     reversed.addNodeAfter(cursor.getInfo()); 
     cursor = cursor.getNodeAfter(); 
    } 

    source = reversed; 
    return source; 
} 

Answer 5

Я называю это "вишня сбор". Идея состоит в том, чтобы свести к минимуму количество свопов. Переключение происходит между индексом ближнего и дальнего. Его алгоритм с двумя проходами.

(Odd length) A -> B -> C -> D -> E 
    (Even length) A -> B -> C -> D 

    Pre-Condition: N >= 2 

    Pass 1: Count N, the number of elements 

    Pass 2: 
      for(j=0 -> j<= (N/2 -1)) 
      { 
       swap(j, (N-1)-j) 
      } 

Пример 1:

For above Odd length list, N = 5 and there will be two swaps 

     when j=0, swap(0, 4) //post swap state: E B C D A 
     when j=1, swap(1, 3) //post swap state: E D C B A 


    The mid point for odd length lists remains intact. 

Пример 2:

For above Even length list, N = 4 and there will be two swaps 

     when j=0, swap(0, 3) //post swap state: D B C A 
     when j=1, swap(1, 2) //post swap state: D C B A 

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

Answer 6

Реверсирование однократно связанный список с помощью итерации

current = head //point current pointer to head of the linked list 

while(current != NULL) 
{ 
forward = current->link; //point to the next node 
fforward = forward->link; //point the next node to next node 
fforward->link = forward;//1->2->3,,,,,,,,,this will point node 3 to node 2 
forward->link = current; //this will point node 2 to node 1 
if(current == head) 
current->link = NULL;// if current pointer is head pointer it should point to NULL while reversing 

current = current->link; //traversing the list 
} 
head = current; //make current pointer the head pointer 

Answer 7

list_t *reverse(list_t *a) 
    { 
    list_t *progress = NULL; 
    while(a) 
    { 
     list_t *b; //b is only a temporary variable (don't bother focusing on it) 
     b = a->next; 
     a->next = progress; //because a->next is assigned to another value, we must first save a->next to a different variable (to be able to use it later) 
     progress = a; //progress is initially NULL (so a->next = NULL (because it is the new last element in the list)) 
     a = b; //we set a to b (the value we saved earlier, what a->next was before it became NULL) 
     /* 
     now, at next iteration, progress will equal a, and a will equal b. 
     so, when I assign a->next = progress, I really say, b->next = a. 
     and so what we get is: b->a->NULL. 
     Maybe that gives you an idea of the picture? 
     What is important here is: 
      progress = a 
     and 
      a = b 
     Because that determines what a->next will equal: 
      c->b->a->0 
     a's next is set to 0 
     b's next is set to a 
     c's next is set to b 
     */ 
    } 
    return progress; 
    } 

Answer 8

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

псевдокод:

function reverseList(List X) RETURNS List 
    Y = null 
    WHILE X <> null 
     t = X.next 
     X.next = Y 
     Y = X 
     X = t 
    ENDWHILE 
    RETURN Y 
ENDfunction 

Если вы хотите оставить первоначальный список ненарушенных, то вы можете закодировать копирование версии рекурсивно с использованием вспомогательной функции.

function reverseList(List X) RETURNS List 
    RETURN reverseListAux(X, null) 
ENDfunction 

function reverseListAux(List X, List Y) RETURNS List 
    IF X = null THEN 
     RETURN Y 
    ELSE 
     RETURN reverseListAux(X.next, makeNode(X.data, Y)) 
ENDfunction 

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

function reverseList(List X) RETURNS List 
    Y = null 
    WHILE X <> null 
    Y = makeNode(x.data, Y) 
    X = X.next 
    ENDWHILE 
    RETURN Y 
ENDfunction