在Java中递归地反转链表
在Java中递归地反转链表
提问于 2008-12-10 01:51:59
我已经在一个类的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);
}我在这里的时候，有没有人看到这条路线有什么问题？
回答 28
Stack Overflow用户
发布于 2009-08-09 16:52:16
我进行了一半(直到null，和plinth建议的一个节点)，但在进行递归调用后丢失了踪迹。然而，在阅读了plinth的帖子后，我得出了以下结论：
Node reverse(Node head) {
// if head is null or only one node, it's reverse of itself.
if ( (head==null) || (head.next == null) ) return head;
// reverse the sub-list leaving the head node.
Node reverse = reverse(head.next);
// head.next still points to the last element of reversed sub-list.
// so move the head to end.
head.next.next = head;
// point last node to nil, (get rid of cycles)
head.next = null;
return reverse;
}Stack Overflow用户
发布于 2011-09-15 11:05:38
这是另一个递归解决方案。与其他一些递归函数相比，它在递归函数中包含的代码更少，因此它可能会更快一点。这是C#，但我相信它会非常相似。
class Node<T>
{
Node<T> next;
public T data;
}
class LinkedList<T>
{
Node<T> head = null;
public void Reverse()
{
if (head != null)
head = RecursiveReverse(null, head);
}
private Node<T> RecursiveReverse(Node<T> prev, Node<T> curr)
{
Node<T> next = curr.next;
curr.next = prev;
return (next == null) ? curr : RecursiveReverse(curr, next);
}
}Stack Overflow用户
发布于 2010-03-04 10:26:06
我认为这是更简洁的解决方案，类似于LISP
// Example:
// reverse0(1->2->3, null) =>
// reverse0(2->3, 1) =>
// reverse0(3, 2->1) => reverse0(null, 3->2->1)
// once the first argument is null, return the second arg
// which is nothing but the reveresed list.
Link reverse0(Link f, Link n) {
if (f != null) {
Link t = new Link(f.data1, f.data2);
t.nextLink = n;
f = f.nextLink; // assuming first had n elements before,
// now it has (n-1) elements
reverse0(f, t);
}
return n;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/354875
复制相关文章
相似问题
腾讯云开发者
