java - 递归地反转单链接、基于哨兵的列表(有效，但不是以我希望的方式)

Question

我正在准备面试，并编写了这个简单的函数来递归地反转单链表。第一个节点是哨兵节点，head。以下代码适用于:list.reverse(list.head.next)，但如果我只传递它head，我似乎无法让它工作。

public Node<T> reverse(Node<T> current)
{
    if (current == null)
        return head;

    if (current.next == null)
    {
        head.next = current;
        return current;
    }

    reverse(current.next).next = current;
    current.next = null;
    return current;
}

我认为当我传递它 head 而不是 head.next 时它不起作用，因为我说 current.next = null，但即使我检查是否 current == head 或 if current.data == null 并且仅在这些情况下使用 current.next = null不是真的，它仍然不起作用。我确信有一个非常简单的修复方法，但我现在还没有看到它。

上面的如果通过 head 返回一个空列表，如果进行了建议的更改，则根本无法完成运行，但我没有收到任何错误。

Answer 1

(已编辑) 我现在有点明白你的问题了:

简单来说，哨兵头只是充当指向第一个节点的指针，而不是链表的一部分。因此不会参与逆向过程，需要单独处理。

这意味着原始列表如下所示:

HEAD -> a -> b -> c -> null

反转后，它应该看起来像

HEAD -> c -> b -> a -> null

简而言之，它应该看起来像(假设您的代码在传入 head.next 时已经可以工作)

public Node<T> reverse(Node<T> current)
{
    if (current == head) {
        return reverse(current.next);
    }

    // rest of your original code.
}

<小时/>

进一步的建议:

您的reverse()方法作为列表类的公共(public)实例方法，不应接受当前节点，因为它在概念上对调用者来说毫无意义。

我相信你应该保护这个方法，这意味着:

public void reverse() {
    this.head = reverseInternal(head);
}

private Node<T> reverseInternal(Node<T> node) {
    // your original reverse logic
}

有了这样的封装，当你传入哨兵头时，你甚至不需要费力地了解如何让你的反向工作:你可以简单地在你的 public 中调用 reverseInternal(head.next) reverse() 方法。