java反转单链表

Question

在一次求职面试中，我被要求撤销一个单链表。以下是我的解决方案：

public class E<T>{
    private E<T> next;
    private T val;

    private E(T val) {
        this.val = val;
    }

    public static <T> E<T> createNode(T val){
        return new E<T>(val);
    }

    public E<T> add(E<T> next){
        E<T> current = this;
        while(current.next != null){
            current = current.next;
        }
        current.next = next;
        return this;
    }

    public E<T> reverse(){
        if(this.next == null)
            return this;
        E<T> previous = new E<>(this.val); //<----- HERE
        E<T> current = this.next;
        while(current != null){ 
            E<T> tmp = current.next;
            this.val = current.val;
            this.next = previous;
            current.next = previous;
            previous = current;
            current = tmp;
        }
        return this;
    }
}

但它看起来确实很难看。我不明白该如何处理的问题是，我们最初只有this引用，而我们不能将其分配给任何东西（当时我们只是以一个循环结束）。这就是我创建新节点的原因。但这看起来是一个糟糕的解决办法。有没有“真正的方法”可以做到这一点

Answer 1

一种方法是使用递归：

public E<T> reverse() {
    if (this.next == null) return this;
    E<T> node = this.next.reverse();
    this.next.next = this;
    this.next = null;
    return node;
}

我确实测试过它，它工作得很顺利，但是如果列表太长，您可能会遇到麻烦：调用堆栈可能会爆炸

迭代方式：

public E<T> reverse() {
    E<T> previous = null;
    E<T> current = this;
    E<T> next = this.next;
    while (next != null) {
        current.next = previous;
        previous = current;
        current = next;
        next = current.next;
    }
    current.next = previous; // We haven't reversed the last node yet.
    return current;
}

同样，这已经过测试，并产生了预期的效果

此外，可以改进add方法，使其花费恒定的时间：

public E<T> add(E<T> node) {
    node.next = this;
    return node;
}

Answer 2

您将有权访问头部节点。所以，你可以从头部节点开始，改变链接的方向直到结束。最后，让你的头->；下一个节点为null，最后一个节点为HEAD

差不多吧。（我还没有测试过……只是用一些伪代码编写了这个想法）

cur = head.next;
prev = head;

while(cur)
{
    next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
} 

head.next = null;
head = cur;

Answer 3

下面是一段解决问题的递归代码：

public E<T> reverse() {
    if(next == null) return this;
    else {
        E<T> r = next.reverse();
        this.next = null;
        r.add(this);
        return r;
    }
}

下面是一段以迭代方式解决问题的代码：

public E<T> reverse() {
    E<T> n = this;
    E<T> last = null;

    while(n.next != null) {
        E<T> temp = n.next;
        n.next = last;
        last = n;
        n = temp;
    }

    n.next = last;

    return n;
}

Answer 4

如果您出于某种原因不能使用像Collections这样的collection实用程序功能。正如中东新闻社所说的那样，你可以大致执行以下步骤：

public Iterable<T> Reverse<T>(Iterable<T> queue)
{
    Stack<T> stack = new Stack<T>();  
    while(!queue.isEmpty())
       stack.push(queue.pop());

    return stack;
}

（*这是伪代码，不是真正的实现）

编辑：就地版本

public void Reverse<T>(Iterable<T> queue)
{   
    //todo: add null check
    Stack<T> stack = new Stack<T>();  
    while(!queue.isEmpty())
       stack.push(queue.pop());

    while(!stack.isEmpty())
       queue.append(stack.pop());
}