递归地反转Java中的链表

Reversing a linked list in Java, recursively

提问by sdellysse

I have been working on a Java project for a class for a while now. It is an implementation of a linked list (here called AddressList, containing simple nodes called ListNode). The catch is that everything would have to be done with recursive algorithms. I was able to do everything fine sans one method: public AddressList reverse()

我一直在为一个班级的 Java 项目工作一段时间。它是一个链表的实现（这里称为AddressList，包含称为的简单节点ListNode）。问题是一切都必须用递归算法来完成。我能够在没有一种方法的情况下做任何事情：public AddressList reverse()

ListNode:

列表节点：

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

Right now my reversefunction just calls a helper function that takes an argument to allow recursion.

现在我的reverse函数只是调用一个辅助函数，它接受一个参数来允许递归。

public AddressList reverse(){
  return new AddressList(this.reverse(this.head));
}

With my helper function having the signature of private ListNode reverse(ListNode current).

我的辅助函数具有private ListNode reverse(ListNode current).

At the moment, I have it working iteratively using a stack, but this is not what the specification requires. I had found an algorithm in C that recursively reversed and converted it to Java code by hand, and it worked, but I had no understanding of it.

目前，我使用堆栈迭代地工作，但这不是规范所要求的。我在 C 中找到了一种算法，可以递归地将其反转并手动将其转换为 Java 代码，并且它有效，但我不了解它。

Edit: Nevermind, I figured it out in the meantime.

编辑：没关系，我在此期间想通了。

private AddressList reverse(ListNode current, AddressList reversedList){
  if(current == null) 
      return reversedList;
  reversedList.addToFront(current.getData());
  return this.reverse(current.getNext(), reversedList);
}

While I'm here, does anyone see any problems with this route?

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

采纳答案by plinth

There's code in one reply that spells it out, but you might find it easier to start from the bottom up, by asking and answering tiny questions (this is the approach in The Little Lisper):

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

1. What is the reverse of null (the empty list)? null.
2. What is the reverse of a one element list? the element.
3. What is the reverse of an n element list? the reverse of the rest of the list followed by the first element.

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

回答by Ari Ronen

I was asked this question at an interview and was annoyed that I fumbled with it since I was a little nervous.

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

This should reverse a singly linked list, called with reverse(head,NULL); so if this were your list:

这应该反转一个单链表，用 reverse(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
    }
    

edit: ive done like 6 edits on this, showing that it's still a little tricky for me lol

编辑：我对此做了 6 次编辑，这表明它对我来说仍然有点棘手，哈哈

回答by Devesh Rao

The algo will need to work on the following model,

该算法将需要在以下模型上工作，

• keep track of the head
• Recurse till end of linklist
• Reverse linkage

• 跟踪头部
• 递归到链表结束
• 反向联动

Structure:

结构：

Head    
|    
1-->2-->3-->4-->N-->null

null-->1-->2-->3-->4-->N<--null

null-->1-->2-->3-->4<--N<--null

null-->1-->2-->3<--4<--N<--null

null-->1-->2<--3<--4<--N<--null

null-->1<--2<--3<--4<--N<--null

null<--1<--2<--3<--4<--N
                       |
                       Head

Code:

代码：

public ListNode reverse(ListNode toBeNextNode, ListNode currentNode)
{               
        ListNode currentHead = currentNode; // keep track of the head

        if ((currentNode==null ||currentNode.next==null )&& toBeNextNode ==null)return currentHead; // ignore for size 0 & 1

        if (currentNode.next!=null)currentHead = reverse(currentNode, currentNode.next); // travarse till end recursively

        currentNode.next = toBeNextNode; // reverse link

        return currentHead;
}

Output:

输出：

head-->12345

head-->54321

回答by Devesh Rao

I got half way through (till null, and one node as suggested by plinth), but lost track after making recursive call. However, after reading the post by plinth, here is what I came up with:

我已经完成了一半（直到空值，还有一个节点，如底座所建议的那样），但是在进行递归调用后失去了踪迹。但是，在阅读了 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;
}

回答by Devesh Rao

void reverse(node1,node2){
if(node1.next!=null)
      reverse(node1.next,node1);
   node1.next=node2;
}
call this method as reverse(start,null);

回答by Swapneel Patil

I think this is more cleaner solution, which resembles LISP

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

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

回答by readdear

I know this is an old post, but most of the answers are not tail recursive i.e. they do some operations after returning from the recursive call, and hence not the most efficient.

我知道这是一篇旧帖子，但大多数答案都不是尾递归的，即它们在从递归调用返回后执行一些操作，因此不是最有效的。

Here is a tail recursive version:

这是一个尾递归版本：

public Node reverse(Node previous, Node current) {
    if(previous == null)
        return null;
    if(previous.equals(head))
        previous.setNext(null);
    if(current == null) {    // end of list
        head = previous;
        return head;
    } else {
                    Node temp = current.getNext();
        current.setNext(previous);
        reverse(current, temp);
    }
    return null;    //should never reach here.
} 

Call with:

致电：

Node newHead = reverse(head, head.getNext());

回答by Michael

public class Singlelinkedlist {
  public static void main(String[] args) {
    Elem list  = new Elem();
    Reverse(list); //list is populate some  where or some how
  }

  //this  is the part you should be concerned with the function/Method has only 3 lines

  public static void Reverse(Elem e){
    if (e!=null)
      if(e.next !=null )
        Reverse(e.next);
    //System.out.println(e.data);
  }
}

class Elem {
  public Elem next;    // Link to next element in the list.
  public String data;  // Reference to the data.
}

回答by KNA

public Node reverseListRecursive(Node curr)
{
    if(curr == null){//Base case
        return head;
    }
    else{
        (reverseListRecursive(curr.next)).next = (curr);
    }
    return curr;
}

回答by PointZeroTwo

Here's yet another recursive solution. It has less code within the recursive function than some of the others, so it might be a little faster. This is C# but I believe Java would be very similar.

这是另一个递归解决方案。它在递归函数中的代码比其他一些函数少，所以它可能会快一点。这是 C#，但我相信 Java 会非常相似。

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