java - 递归反转链表

Question

这个问题已经有答案了:

Reversing a linked list in Java, recursively (33 个回答)

已关闭 7 年前。

我正在尝试使用递归调用反转 LinkedList，请让我知道哪里出错了，我无法捕获反转的 LL 头。LLNode是一个链表节点，ReverseLLRecursively.reverse是我编写的用于反转的函数。

这是我的代码:

public class LLNode {
    private int data;
    private LLNode next;

    public LLNode(int data, LLNode next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public LLNode getNext() {
        return next;
    }

    public void setNext(LLNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return data + "->[" + (next!=null?next.data:"") + "]";
    }
}

public class ReverseLLRecursively {

    public static LLNode newHead = new LLNode(-1, null);

    public static LLNode reverse(LLNode head, LLNode newHead) {
        if(head==null || head.getNext()==null) {
            newHead = head;
            return head;
        }

        LLNode node = reverse(head.getNext(), newHead);
        node.setNext(head);
        head.setNext(null);
        return node.getNext();
    }

    public static void main(String[] args) {
        LLNode ll = new LLNode(1,new LLNode(2, new LLNode(3,  new LLNode(3, new LLNode(2,  new LLNode(3, null))))));

        reverse(ll , newHead);
        System.out.println(newHead);

    }

}

Answer 1

您使问题过于复杂化并使用与静态成员同名的局部变量。这应该更简单:

public static LLNode reverse(LLNode previous) {
    if(previous==null) {
        return null;
    }
    LLNode toReturn = (previous->getNext() == null) ? previous : reverse(previous.getNext());
    previous.getNext().setNext(previous);
    return toReturn;
}

请注意，toReturn 将是新的头。