首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在Java中递归地反转链表

在Java中递归地反转链表
EN

Stack Overflow用户
提问于 2008-12-10 01:51:59
回答 28查看 185K关注 0票数 107

我已经在一个类的Java项目上工作了一段时间了。它是链表(这里称为AddressList,包含称为ListNode的简单节点)的实现。问题是,所有的事情都必须用递归算法来完成。除了一种方法以外,我可以做所有的事情:public AddressList reverse()

ListNode:

代码语言:javascript
复制
public class ListNode{
  public String data;
  public ListNode next;
}

现在,我的reverse函数只调用了一个助手函数,该函数接受一个参数来允许递归。

代码语言:javascript
复制
public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

我的帮助器函数具有private ListNode reverse(ListNode current)签名。

目前,我使用堆栈让它迭代工作,但这不是规范所要求的。我在C语言中发现了一种算法,可以手动将其递归地反转并转换为Java代码,它是有效的,但我对此一无所知。

编辑:不要紧,我在这段时间弄明白了。

代码语言:javascript
复制
private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) 
      return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

我在这里的时候,有没有人看到这条路线有什么问题?

EN

回答 28

Stack Overflow用户

发布于 2009-08-09 16:52:16

我进行了一半(直到null,和plinth建议的一个节点),但在进行递归调用后丢失了踪迹。然而,在阅读了plinth的帖子后,我得出了以下结论:

代码语言:javascript
复制
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;
}
票数 24
EN

Stack Overflow用户

发布于 2011-09-15 11:05:38

这是另一个递归解决方案。与其他一些递归函数相比,它在递归函数中包含的代码更少,因此它可能会更快一点。这是C#,但我相信它会非常相似。

代码语言:javascript
复制
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);
    }
}
票数 9
EN

Stack Overflow用户

发布于 2010-03-04 10:26:06

我认为这是更简洁的解决方案,类似于LISP

代码语言:javascript
复制
// 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;
}
票数 7
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/354875

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档