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

data-structures java recursion linked-list

2022-08-31 09:47:28

我已经为一个类的Java项目工作了一段时间。它是链表的实现（这里称为，包含称为的简单节点）。问题是，一切都必须使用递归算法来完成。我能够用一种方法把所有事情都做好：AddressListListNodepublic AddressList reverse()

列表节点：

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

当我在这里时，有人看到这条路线有任何问题吗？

答案 1

一个回复中有代码可以拼写出来，但你可能会发现，通过提出和回答小问题，从下往上开始更容易（这是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

在一次采访中，我被问到这个问题，因为我有点紧张，所以我很生气。

这应该反转一个单链表，用反向（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次编辑，表明这对我来说仍然有点棘手，哈哈