问题

我一直在为一个类的Java项目工作。它是链表的实现(此处称为AddressList,包含名为ListNode的简单节点)。问题在于,所有事情都必须通过递归算法来完成。我能做的一切都很好,没有一种方法:public AddressList reverse()

ListNode:

public class ListNode{
  public String data;
  public ListNode next;
}

现在myreverse函数只调用一个辅助函数,它接受一个允许递归的参数。

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

虽然我在这里,有没有人看到这条路线有任何问题?


#1 热门回答(305 赞)

在一个回复中有代码说明了这一点,但你可能会发现通过询问和回答微小的问题(这是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;
}

#2 热门回答(28 赞)

我在接受采访时被问到这个问题并且因为我有点紧张而感到烦恼。

这应该反转一个单链表,用反向调用(head,NULL);所以如果这是你的清单:

1->2->3->4->5->null
it would become:
5->4->3->2->1->null
//Takes as parameters a node in a linked list, and p, the previous node in that list
    //returns the head of the new list
    Node reverse(Node n,Node p){   
        if(n==null) return null;
        if(n.next==null){ //if this is the end of the list, then this is the new head
            n.next=p;
            return n;
        }
        Node r=reverse(n.next,n);  //call reverse for the next node, 
                                      //using yourself as the previous node
        n.next=p;                     //Set your next node to be the previous node 
        return r;                     //Return the head of the new list
    }

编辑:香港专业教育学院对此做了6次编辑,表明这对我来说仍然有点棘手


#3 热门回答(21 赞)

我得到了一半(直到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;
}

原文链接