递归地反转Java中的链表
我已经在一个类的Java项目上工作了一段时间。它是链表(此处称为AddressList
,包含称为的简单节点ListNode
)的实现。问题是,一切都必须使用递归算法来完成。我可以用一种方法来做所有的事情:public AddressList reverse()
ListNode:
public class ListNode{
public String data;
public ListNode next;
}
现在,我的reverse
函数只是调用一个带有参数以允许递归的辅助函数。
public AddressList reverse(){
return new AddressList(this.reverse(this.head));
}
我的助手功能具有的签名private ListNode reverse(ListNode current)
。
目前,我使用堆栈来迭代工作,但这不是规范所要求的。我在C语言中找到了一种算法,该算法可以递归地将其递归逆转并将其转换为Java代码,并且可以正常工作,但是我对此并不了解。
编辑:没关系,与此同时我也想通了。
private AddressList reverse(ListNode current, AddressList reversedList){
if(current == null)
return reversedList;
reversedList.addToFront(current.getData());
return this.reverse(current.getNext(), reversedList);
}
当我在这里时,有人看到此路线有任何问题吗?
-
在一个答复中有代码将其说明清楚,但是你可能会发现,通过问和回答一些微小的问题(这是The Little Lisper中的方法),更容易从头开始。
- null(空列表)的反向是什么?空值。
- 一个元素列表的反向作用是什么?元素。
n元素列表的反向操作是什么?列表其余部分的倒序,后跟第一个元素。
public ListNode Reverse(ListNode list) { if (list == null) return null; // first question if (list.next == null) return list; // second question // third question - in Lisp this is easy, but we don't have cons // so we grab the second element (which will be the last after we reverse it) ListNode secondElem = list.next; // bug fix - need to unlink list from the rest or you will get a cycle list.next = null; // then we reverse everything from the second element on ListNode reverseRest = Reverse(secondElem); // then we join the two lists secondElem.next = list; return reverseRest; }
-
单链表反转 递归法Java实现
2020-04-29 关注 1 浏览1300 1答案
-
Java,递归地反转数组
2021-01-30 关注 0 浏览88 1答案
-
手写代码:反转链表 (Java 版)
2020-01-31 关注 0 浏览735 1答案
-
单链表反转 遍历法Java实现
2020-04-29 关注 1 浏览1023 1答案
-
反转python中的链表
2021-01-29 关注 0 浏览78 1答案
-
反转链表
2022-03-03 关注 0 浏览41 1答案
-
反转链表
2021-10-21 关注 0 浏览80 1答案
-
链表反转
2022-03-03 关注 0 浏览28 1答案
-
如下代码是实现反转链表的一部分代码:反转链表为:输入一个链表的头节点,反转...
2022-03-02 关注 0 浏览39 1答案
-
单向链表的反转
2021-10-21 关注 0 浏览159 1答案