我试图使用递归来反转链表。我得到了解决方案，但无法让它在网上找到以下问题。
使用递归反转链表，但函数应为void返回类型。
我能够实现返回类型为Node的函数。以下是我的解决方案。
public static Node recursive(Node start) {
// exit condition
if(start == null || start.next == null)
return start;
Node remainingNode = recursive(start.next);
Node current = remainingNode;
while(current.next != null)
current = current.next;
current.next = start;
start.next = null;
return remainingNode;
}
我无法想象这个问题是否会有这样的解决方案。
有什么建议吗？
经过测试，它是有效的（假设您有自己的链表实现，其中包含知道next节点的Node）。
public static void reverse(Node previous, Node current) {
//if there is next node...
if (current.next != null) {
//...go forth and pwn
reverse(current, current.next);
}
if (previous == null) {
// this was the start node
current.next= null;
} else {
//reverse
current.next= previous;
}
}
你称之为
reverse(null, startNode);
public void recursiveDisplay(Link current){
if(current== null)
return ;
recursiveDisplay(current.next);
current.display();
}
static StringBuilder reverseStr = new StringBuilder();
public static void main(String args[]) {
String str = "9876543210";
reverse(str, str.length() - 1);
}
public static void reverse(String str, int index) {
if (index < 0) {
System.out.println(reverseStr.toString());
} else {
reverseStr.append(str.charAt(index));
reverse(str, index - 1);
index--;
}
}
这应该能在中工作
static void reverse(List list, int p) {
if (p == list.size() / 2) {
return;
}
Object o1 = list.get(p);
Object o2 = list.get(list.size() - p - 1);
list.set(p, o2);
list.set(list.size() - p - 1, o1);
reverse(list, p + 1);
}
不过为了使用LinkedList提高效率，应该对其进行重构以使用ListIterator
我不熟悉Java，但这里有一个C++版本。在反转列表之后，列表的头部仍然保留，这意味着该列表仍然可以从旧的列表头部List* h访问。
void reverse(List* h) {
if (!h || !h->next) {
return;
}
if (!h->next->next) {
swap(h->value, h->next->value);
return;
}
auto next_of_next = h->next->next;
auto new_head = h->next;
reverse(h->next);
swap(h->value, new_head->value);
next_of_next->next = new_head;
h->next = new_head->next;
new_head->next = nullptr;
}
改为尝试此代码-它实际上可以使用
public static ListElement reverseListConstantStorage(ListElement head) {
return reverse(null,head);
}
private static ListElement reverse(ListElement previous, ListElement current) {
ListElement newHead = null;
if (current.getNext() != null) {
newHead = reverse(current, current.getNext());
} else {//end of the list
newHead=current;
newHead.setNext(previous);
}
current.setNext(previous);
return newHead;
}
public static Node recurse2(Node node){
Node head =null;
if(node.next == null) return node;
Node previous=node, current = node.next;
head = recurse2(node.next);
current.next = previous;
previous.next = null;
return head;
}
调用函数时，将返回值分配如下：
list.head=recurse2(list.head);
下面的函数是基于darijan选择的答案，我所做的只是添加2行代码，以便它适合你们想要工作的代码：
public void reverse(Node previous, Node current) {
//if there is next node...
if (current.next != null) {
//...go forth and pwn
reverse(current, current.next);
}
else this.head = current;/*end of the list <-- This line alone would be the fix
since you will now have the former tail of the Linked List set as the new head*/
if (previous == null) {
// this was the start node
current.next= null;
this.tail = current; /*No need for that one if you're not using a Node in
your class to represent the last Node in the given list*/
} else {
//reverse
current.next= previous;
}
}
此外，我已经将其更改为一个非静态函数，因此使用它的方法是：myLinkedList.reverse(null, myLinkedList.head);
这是我的版本-void ReverseWithRecursion（Node currentNode）-这是LinkListDemo类的方法，因此头部可以访问
- 基本情况-如果Node为null，则不执行任何操作并返回。如果Node->Next为null，则"Make it head"并返回
-
其他情况-反转currentNode的下一个。
public void ReverseWithRecursion(Node currentNode){ if(currentNode == null) return; if(currentNode.next == null) {head = currentNode; return;} Node first = currentNode; Node rest = currentNode.next; RevereseWithRecursion(rest); first.next.next = first; first.next = null; }
你这样称呼它-
LinkListDemo ll = new LinkListDemo(); // assueme class is available
ll.insert(1); // Assume method is available
ll.insert(2);
ll.insert(3);
ll.ReverseWithRecursion(ll.head);
假设您有一个Node类，如下所示：
public class Node
{
public int data;
public Node next;
public Node(int d) //constructor.
{
data = d;
next = null;
}
}
和一个linkedList类，您在该类中声明了一个head节点，以便您在linkedList类中创建的方法可以访问它。方法"ReverseLinkedList"将Node作为参数，并反转ll。
您可以通过考虑1->2作为linkedList。其中node=1，node.next=2。
public class LinkedList
{
public Node? head; //head of list
public LinkedList()
{
head = null;
}
public void ReverseLinkedList(Node node)
{
if(node==null)
{
return;
}
if(node.next==null)
{
head = node;
return;
}
ReverseLinkedList(node.next); // node.next = rest of the linkedList
node.next.next = node; // consider node as the first part of linkedList
node.next = null;
}
}
我能想到的最简单的方法是：
public static <T> void reverse( LinkedList<T> list )
{
if (list.size() <= 1) {
return;
}
T first = list.removeFirst();
reverse( list);
list.addLast( first );
}