这个链表反向实现是如何工作的

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
}

上箱子！

（我建议查看反向链接列表中的代码，它是相同的概念，但更容易理解，并且没有此实现的假头节点。

---

我知道我说"画盒子就行了"。所以，在你又发表了一些评论之后，我画了盒子。（我假装我回到了大学;-）

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

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

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

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