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

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

1> plinth..：

---

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

---

特殊情况的例外情况.为什么使用一个可以通过if测试的已知条件的捕获？

---

哇,我喜欢整个"三个问题"的事情.

---

谢谢.这个小问题应该是学习Lisp的基础.它也是一种隐藏来自newbs的感应的方式,这基本上就是这种模式.如果你真的想解决这类问题,我建议你阅读Little Lisper.

---

我相信你不需要创建变量:secondElem,因为list.next仍然是secondElem.在"ListNode reverseRest = Reverse(secondElem);"之后,您可以先执行"list.next.next = list",然后执行"list.next = null".就是这样.

---

你能解释一下为什么list.next = null？我试图了解周期但没有得到.

---

@Rohit list.next = null打破了元素与其后续元素之间的连接.如果没有它,您将在此元素和后续元素之间进行循环.

2> Ari Ronen..：

---

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

这应该反转一个单链表,用反向调用(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次编辑,显示它对我来说仍然有点棘手lol

---

在一次采访中,我会对"必须递归"的要求感到有点恼火,说实话,如果指定了Java.否则我会去p = null; while(n.next!= null){n2 = n.next; n.next = p; p = n; n = n2;} n.next = p; 返回 O(N)堆栈用于鸟类.

3> 小智..：

---

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

4> PointZeroTwo..：

---

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

class Node
{
    Node next;
    public T data;
}

class LinkedList
{
    Node head = null;

    public void Reverse()
    {
        if (head != null)
            head = RecursiveReverse(null, head);
    }

    private Node RecursiveReverse(Node prev, Node curr)
    {
        Node next = curr.next;
        curr.next = prev;
        return (next == null) ? curr : RecursiveReverse(curr, next);
    }
}

5> 小智..：

---

算法将需要处理以下模型,

跟踪头部

递归到链接列表的结尾

反向连接

结构体:

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

码:

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

输出:

head-->12345

head-->54321

6> Swapneel Pat..：

---

我认为这是更清洁的解决方案,类似于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;
}

7> 小智..：

---

我知道这是一个旧帖子,但大多数答案都不是尾递归,即它们在从递归调用返回后执行一些操作,因此效率最高.

这是一个尾递归版本:

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

致电:

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

---

你在方法中引用了一个名为"head"的变量,但是没有在任何地方声明.