反转链表的问题

Question

我正在尝试了解 linked 列表，这对我来说没什么挑战性。我正在尝试使用递归方法反转 link 列表。这是我的代码：

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);


    }
}

我遇到的问题是反向方法。当该方法结束时，它只有 returns 最后一个节点的值为 "First"。通过整个递归，remainingNode 仅保留并返回基本情况的值，这让我感到困惑。我将它排除在外，以便在节点中进一步移动。执行该方法后，newList 仅保留一个节点，下一个节点为 null，并且该节点现在是头。我假设它会反转 linkedlist 的顺序为 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;
}

反转链表的问题

Issues with reversing the linkedlist

java

algorithm

linked-list

nodes