gpt4 book ai didi

java - 反转链表的问题

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:03:12 25 4
gpt4 key购买 nike

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

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。我做错了什么?

最佳答案

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

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

关于java - 反转链表的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30720573/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com