Как работает эта обратная реализация связанного списка?

Question

Я пытаюсь понять, как обратный LinkedList код работает ниже ...

public void reverse(Node<T> h) { 
    Node<T> d = new Node<T>(); 
    Node<T> t; 
    while (h.next != null) { 
    t = h.next; //temp nodes points to h.next (1st item in list) 
    h.next = t.next; //h.next bypasses first node in list. 
    t.next = d.next; //t.next points to d.next.. where is d.next pointing to? 
    d.next = t; //d.next now points to t. 
    } 
    h.next = d.next; 
    } 

Как этот процесс работает?

Диаграмма была бы удивительной. Кажется, что узлы из одного списка выскользнули и вошли в новый список? В этом случае h указал на то, что список отменен?

Answer 1

Update себе, а также редакция вызов:

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

Переписывая это, чтобы избежать бесполезного d.next и сфера t лучше, делает его более легким (и возможно для меня), чтобы следовать:

public void reverse(Node<T> h) { // draw H under first node 
    Node<T> d = null 
    while (h.next != null) { 
    Node<T> t = h.next; // draw T under box at end of H arrow (remove any previous T) 
    h.next = t.next;  // change arrow from H to end where arrow from box above T ends (no arrow for last element) 
    t.next = d;   // draw arrow from box above T to box D is under (no arrow for first element) 
    d = t;    // draw D under box (remove any previous D) 
    } 
    h.next = d;   // draw arrow from H to box D is under 
} 

На к ящикам!

(я бы рекомендовал смотреть на код в Reverse a Linked-List, это та же концепция, но легче следовать, и не имеет поддельный головной узел этой реализации.)

---

I знаю, что я сказал: «просто нарисуйте коробки». Итак, после нескольких ваших комментариев, я нарисовал коробки. (Я сделал вид, что я был в колледже ;-)

Однако я не могу заставить его работать либо. Я даже пробовал круги.

Я подозреваю, что код Размещенное не рабочая реализация (которая в настоящее время является открытым вызовом для других людей в настоящее время доказать, что я неправ, по крайней мере, она может держать этот вопрос открытым ;-)

Я не смог использовать его для изменения списка из 2, 3 или 4 элементов в длину после нескольких попыток (хотя мне удалось успешно использовать [более интуитивный] код, представленный в Reverse a Linked-List).

Я считаю, что есть недостаток в использовании h.next вместо h в качестве узла «корень». Возможно, автору приходится вернуть void с фиктивным узлом и побочным эффектом? Но в этом случае линия h.next = t.next все еще, кажется, нарушает алгоритм.