这种反转链表的方法是否有问题

Question

public static Node reverse(Node curr, Node ogHead) {
// base case if we end up back at the head of the original list return
// our new list
if (curr == ogHead) {
return ogHead;
}
// ogHead is initiall setup to be the tail of curr now the current node
// of curr is added to ogHead
ogHead.addNodeAfter(curr.getData());
// set the curr node equal to the next node in the list
curr = curr.getLink();
// call the method again with the new current element and the updated
// new list
reverse(curr, ogHead);
return ogHead;
}

我已经毕业了，但我想知道这是否是反转链表的可接受方式。我相信我最初得到的反馈是它有效，但它本可以更容易测试。curr 参数 i 传递列表的头部，参数 ogHead i 使用 getTail(( 方法传递列表的尾部。

Answer 1

我不能不管这个。下面是递归方法的更好实现，其中节点只是移动即可完成反转：

public static Node reverse(Node curr, Node ogHead) {
// base case if we end up back at the head of the original list return
// our new list
if (curr == ogHead) {
return ogHead;
}
Node oldOgHead = ogHead.link; // Remember what is behind (the original) ogHead
Node nextCurr = curr.link; // Remember curr's successor (which is the starting point for the next recursion)
// Move/insert curr right after ogHead
ogHead.link = curr; // Put curr after ogHead
curr.link = oldOgHead; // Whatever was after ogHead, put it after curr
curr = nextCurr; // Prepare for next recursion
if (curr != null) {
reverse(curr, ogHead);
}
return ogHead;
}

没有浪费内存，只是更新了引用。

Answer 2

代码可能有效。这完全取决于如何实施addNodeAfter。也许您可以通过添加实现来更新问题。

如果是这样，你会得到一个相反顺序的列表，因为你在 ogHead 开始遍历它：

class Node {
private Object data;
private Node link;
public Node(Object data, Node link) {
this.data = data;
this.link = link;
}
public void addNodeAfter(Object data) {
link = new Node(data, link);
}
}

但这只是因为在遍历链表时会创建新节点。原始链表仍将存在。因此，如果您从列表 1->2->3->4 开始，您现在将拥有列表 1->2->3->4->3->2->1，这可能不是您想要的。当仅给定Node的数据部分时，我没有看到任何其他方法可以实现addNodeAfter.