为了账号安全,请及时绑定邮箱和手机立即绑定

以递归方式反转Java中的链表

/ 猿问

以递归方式反转Java中的链表

以递归方式反转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);}

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


查看完整描述

3 回答

?
慕仙森

一个回复中的代码说明了这一点,但是您可能会发现通过询问和回答微小的问题(这是The Little Lisper中的方法)从下往上开始更容易:

  1. null的反转是什么(空列表)?空值。

  2. 单元素列表的反转是什么?元素。

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


查看完整回答
反对 回复 6天前
?
慕斯王

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

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

1-> 2-> 3-> 4-> 5->空它会变成:5-> 4-> 3-> 2-> 1->空
    //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次编辑,显示它对我来说仍然有点棘手lol


查看完整回答
反对 回复 6天前
?
春华秋衣

我得到了一半(直到null,并且由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;}


查看完整回答
反对 回复 6天前

添加回答

回复

举报

0/150
提交
取消
意见反馈 邀请有奖 帮助中心 APP下载
官方微信