1

我试图了解下面的反向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指向正在反转的列表？

4

1 回答 1

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中的代码，它是相同的概念，但更容易理解并且没有此实现的假头节点。）

我知道我说过“只画盒子”。所以，在你的更多评论之后，我画了盒子。（我假装我回到了大学;-)

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

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

I have not been able to use it to reverse a list of 2, 3 or 4 elements in length after several attempts (although I have been able to successfully use the [much more intuitive] code presented in Reverse a Linked-List).

I believe there is a flaw in using h.next instead of h as the "root" node. Perhaps the author is accounting for a void return with a dummy-node and side-effect? But in that case the line h.next = t.next still seems to break the algorithm.

于 2012-06-25T02:34:49.027 回答