java - 这个链表反向实现是如何工作的呢？

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

更新我自己，以及挑战的修订:

该算法确实有效，只是以一种令人困惑的方式编写，并且不包含第一个节点(它仅使用它来产生副作用)，这本身就是一个......有问题的设计。

重写它以避免无用的 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 中的代码，它是相同的概念，但更容易遵循，并且没有此实现的假头节点。)

<小时/>

我知道我说的是“只画方框”。因此，在听取了您的更多评论后，我画了方框。 (我假装回到了大学；-)

但是，我也无法让它工作。我什至尝试过圆圈。

我怀疑发布的代码不是一个有效的实现(这对于其他人来说是一个公开的挑战，现在证明我错了；至少它可以让这个问题保持开放;-)

经过多次尝试，我仍无法使用它来反转长度为 2、3 或 4 个元素的列表(尽管我已经能够成功使用 Reverse a Linked-List 中提供的[更直观的]代码)。

我认为使用 h.next 而不是 h 作为“根”节点存在缺陷。也许作者正在考虑带有虚拟节点和副作用的 void 返回？但在这种情况下，h.next = t.next 行似乎仍然破坏了算法。