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行似乎仍然破坏了算法