这是反转单链表的正确方法吗？

Question

这是我想出的用于反转 Java 中的单链表的代码，我想知道它是否正确完成。我知道它的工作原理是完成它的工作并拥有 O(n) 的运行时间，但这是一种正确的方法还是可以改进的地方？另外，在反转长链表（不使用迭代替代方案）时，我能做些什么来避免堆栈溢出问题，因为当试图反转大小大于 8300 的链表时，它会导致堆栈溢出异常。

private void reverse(Node node) {
    if(node != this.tail) {
        reverse(node.next);
        this.tail.next = new Node(node.item);
        this.tail = this.tail.next;
        this.head = this.head.next;
    } 
}

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

Answer 1

该解决方案似乎不错，但是您不需要使用旧 Node 对象的值创建新的 Node 对象。您可以反转 singly-linked-list in-place 并在 O(n) 时间复杂度内。

public Node reverse(Node head) {
   Node prev = null;
   while(head!= null) {
      Node rem = head.next;
      head.next = prev;
      prev = current;
      current = rem;
   }
   return prev;  // prev is the new head of your linked list
}

如果您不想使用迭代解决方案（尽管我建议这样做），您可以使用下面的递归解决方案：


public Node reverseList(Node node) { // send the head of the list
   if(current == null) return null;

   reverse(current);
   return this.tail;  // now tail is the head and head is the tail
}
    
public Node reverse(Node node) {
    if(node.next == null) {
        this.tail = node;
    } else {
        reverse(node.next).next = node;
        node.next = null;
    }
    return node;
}

我没有关于您的链接列表的足够详细信息，但我假设您有 this.head 和 this.tail 字段。即使 this.tail 未初始化，此解决方案也有效。而且，如果预先赋值，就不需要从头遍历链表了。

这是反转单链表的正确方法吗？

Is this a correct way to reverse a singly linked list?

java

algorithm

singly-linked-list