java - 这种反转链表的方法有问题吗

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 参数传递列表的头部，参数 ogHead 使用 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;
}

不浪费内存，只是更新引用。