java - 反转链表的问题

Question

我正在尝试学习链表，这对我来说挑战不大。我正在尝试使用递归方法反转链接列表。这是我的代码:

public class ListNode {
    Node head = null;

    int nodeCount= 0;

    int counter = 0;

    ListNode(){
        head = null;

    }

    public void insertNode( String name ) {

        if (head == null) {
            head = new Node(name, null);
            nodeCount++;
        } else {
            Node temp = new Node(name, null);
            temp.next = head;
            head = temp;


            nodeCount++;
        }
    }
        public Node reverseTest(Node L){

            // Node current = new Node(null,null);

            if(L == null || L.next ==null){
                return L;
            }

            Node remainingNode =  reverseTest(L.next);
            Node cur = remainingNode;
            while(cur.next !=null){
                cur=cur.next;
            }

            L.next = null;
            cur.next = L;

            return  remainingNode;

        }


    public static void main(String[] args){

        ListNode newList = new ListNode();
        newList.insertNode("First");
        newList.insertNode("Second");
        newList.insertNode("Third");
        newList.insertNode("Fourth");

        newList.reverseTest(newList.head);


    }
}

我遇到的问题是反向方法。当该方法结束时，它只返回值为“First”的最后一个节点。在整个递归过程中，remainingNode 只保存并返回基本情况的值，这让我很困惑。我将它排除在外，以便在节点中进一步移动。执行该方法后，newList 仅保留一个节点，下一个节点为 null，并且该节点现在是头。我假设它将反转链表的顺序为 First --> Second--> Third --> Fourth。我做错了什么？

Answer 1

实际上，这里一切正常。您唯一的问题是在您的主要方法中:您没有得到您的方法的结果。

newList.reverseTest(newList.head);

您需要使用结果实际设置新头:

newList.head = newList.reverseTest(newList.head);

如果您将方法声明为静态的，这会更容易查看:

newList.head = ListNode.reverseTest(newList.head);

---

作为奖励，这里有一个完全递归的等价物:

public static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }

    Node newHead = reverse(head.next);

    // head.next points to the new tail, we push the former head at the end
    head.next.next = head;
    // now head has become the new tail, we cut the end of the list
    head.next = null;

    return newHead;
}