用Java以recursion方式反转链接列表
现在我一直在为一个类的Java项目工作。 它是一个链表的实现（这里叫做AddressList ，包含简单的节点叫做ListNode ）。 问题是，一切都必须用recursionalgorithm来完成。 我能够做的一切都很好的方法之一： public AddressList reverse()
ListNode：
public class ListNode{ public String data; public ListNode next; }
现在我的reverse函数只是调用一个帮助函数，它需要一个参数来允许recursion。
public AddressList reverse(){ return new AddressList(this.reverse(this.head)); }
与我的帮助函数具有private ListNode reverse(ListNode current)的签名。
目前，我有迭代使用堆栈，但这不是规范要求。 我已经find了一个C语言的algorithm，它recursion地反转并手动将其转换为Java代码，并且它工作正常，但是我对此不了解。
编辑：没关系，我在此期间计算出来了。
private AddressList reverse(ListNode current, AddressList reversedList){ if(current == null) return reversedList; reversedList.addToFront(current.getData()); return this.reverse(current.getNext(), reversedList); }
虽然我在这里，有没有人看到这条路线的任何问题？
在一个答复中有代码说明了这一点，但是你可能会发现从底部开始，通过询问和回答小问题（这是Little Lisper的方法）更容易：
- 什么是空（空列表）的相反？ 空值。
- 什么是一个元素列表的相反？ 元素。
- 什么是一个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; }
我在接受采访的时候被问到了这个问题，并且因为我有点紧张而感到烦恼。
这应该反转单向链表，用reverse（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个编辑，显示这对我来说还是有点棘手的
我得到了一半（直到null，还有一个节点由基座build议），但是在recursion调用之后失去了踪迹。 但是，在阅读post后，我想到了：
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; }
这是另一个recursion的解决scheme。 它在recursion函数中的代码less于其他代码中的代码，所以它可能会更快一些。 这是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); } }
我认为这是更清洁的解决scheme，类似于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; }
algorithm将需要在以下模型上工作，
- 跟踪头部
- recursion到链表结束
- 反向链接
结构体：
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
我知道这是一个旧的post，但大多数答案不是尾recursion，即他们从recursion调用返回后做一些操作，因此不是最有效的。
这是一个尾recursion版本：
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());
public Node reverseListRecursive(Node curr) { if(curr == null){//Base case return head; } else{ (reverseListRecursive(curr.next)).next = (curr); } return curr; }
void reverse（node1，node2）{
如果（node1.next！= NULL）
反向（node1.next，节点1）;
node1.next =节点2;
}
调用这个方法为reverse（start，null）;
public void reverse() { head = reverseNodes(null, head); } private Node reverseNodes(Node prevNode, Node currentNode) { if (currentNode == null) return prevNode; Node nextNode = currentNode.next; currentNode.next = prevNode; return reverseNodes(currentNode, nextNode); }
public static ListNode recRev(ListNode curr){ if(curr.next == null){ return curr; } ListNode head = recRev(curr.next); curr.next.next = curr; curr.next = null; // propogate the head value return head; }
反向recursionalgorithm。
public ListNode reverse(ListNode head) { if (head == null || head.next == null) return head; ListNode rHead = reverse(head.next); rHead.next = head; head = null; return rHead; }
通过迭代
public ListNode reverse(ListNode head) { if (head == null || head.next == null) return head; ListNode prev = null; ListNode cur = head ListNode next = head.next; while (next != null) { cur.next = prev; prev = cur; cur = next; next = next.next; } return cur; }
该解决scheme演示了不需要参数。
/** * Reverse the list * @return reference to the new list head */ public LinkNode reverse() { if (next == null) { return this; // Return the old tail of the list as the new head } LinkNode oldTail = next.reverse(); // Recurse to find the old tail next.next = this; // The old next node now points back to this node next = null; // Make sure old head has no next return oldTail; // Return the old tail all the way back to the top }
这里是支持的代码，以certificate这是有效的：
public class LinkNode { private char name; private LinkNode next; /** * Return a linked list of nodes, whose names are characters from the given string * @param str node names */ public LinkNode(String str) { if ((str == null) || (str.length() == 0)) { throw new IllegalArgumentException("LinkNode constructor arg: " + str); } name = str.charAt(0); if (str.length() > 1) { next = new LinkNode(str.substring(1)); } } public String toString() { return name + ((next == null) ? "" : next.toString()); } public static void main(String[] args) { LinkNode head = new LinkNode("abc"); System.out.println(head); System.out.println(head.reverse()); } }
这是一个简单的迭代方法：
public static Node reverse(Node root) { if (root == null || root.next == null) { return root; } Node curr, prev, next; curr = root; prev = next = null; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }
这是一个recursion的方法：
public static Node reverseR(Node node) { if (node == null || node.next == null) { return node; } Node next = node.next; node.next = null; Node remaining = reverseR(next); next.next = node; return remaining; }
由于Java始终是按值传递的，为了在Java中recursion地反转链表，请确保在recursion结束时返回“新头”（返回后的头节点）。
static ListNode reverseR(ListNode head) { if (head == null || head.next == null) { return head; } ListNode first = head; ListNode rest = head.next; // reverse the rest of the list recursively head = reverseR(rest); // fix the first node after recursion first.next.next = first; first.next = null; return head; }
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. }
public Node reverseRec(Node prev, Node curr) { if (curr == null) return null; if (curr.next == null) { curr.next = prev; return curr; } else { Node temp = curr.next; curr.next = prev; return reverseRec(curr, temp); } }
调用using：head = reverseRec（null，head）;
其他人做了什么，在其他职位是一个内容的游戏，我所做的是一个链接列表的游戏，它扭转LinkedList的成员不会扭转成员的价值。
Public LinkedList reverse(LinkedList List) { if(List == null) return null; if(List.next() == null) return List; LinkedList temp = this.reverse( List.next() ); return temp.setNext( List ); }
package com.mypackage; class list{ node first; node last; list(){ first=null; last=null; } /*returns true if first is null*/ public boolean isEmpty(){ return first==null; } /*Method for insertion*/ public void insert(int value){ if(isEmpty()){ first=last=new node(value); last.next=null; } else{ node temp=new node(value); last.next=temp; last=temp; last.next=null; } } /*simple traversal from beginning*/ public void traverse(){ node t=first; while(!isEmpty() && t!=null){ t.printval(); t= t.next; } } /*static method for creating a reversed linked list*/ public static void reverse(node n,list l1){ if(n.next!=null) reverse(n.next,l1);/*will traverse to the very end*/ l1.insert(n.value);/*every stack frame will do insertion now*/ } /*private inner class node*/ private class node{ int value; node next; node(int value){ this.value=value; } void printval(){ System.out.print(value+" "); } } }
解决scheme是：
package basic; import custom.ds.nodes.Node; public class RevLinkedList { private static Node<Integer> first = null; public static void main(String[] args) { Node<Integer> f = new Node<Integer>(); Node<Integer> s = new Node<Integer>(); Node<Integer> t = new Node<Integer>(); Node<Integer> fo = new Node<Integer>(); f.setNext(s); s.setNext(t); t.setNext(fo); fo.setNext(null); f.setItem(1); s.setItem(2); t.setItem(3); fo.setItem(4); Node<Integer> curr = f; display(curr); revLL(null, f); display(first); } public static void display(Node<Integer> curr) { while (curr.getNext() != null) { System.out.println(curr.getItem()); System.out.println(curr.getNext()); curr = curr.getNext(); } } public static void revLL(Node<Integer> pn, Node<Integer> cn) { while (cn.getNext() != null) { revLL(cn, cn.getNext()); break; } if (cn.getNext() == null) { first = cn; } cn.setNext(pn); }
}
static void reverseList(){ if(head!=null||head.next!=null){ ListNode tail=head;//head points to tail ListNode Second=head.next; ListNode Third=Second.next; tail.next=null;//tail previous head is poiniting null Second.next=tail; ListNode current=Third; ListNode prev=Second; if(Third.next!=null){ while(current!=null){ ListNode next=current.next; current.next=prev; prev=current; current=next; } } head=prev;//new head } } class ListNode{ public int data; public ListNode next; public int getData() { return data; } public ListNode(int data) { super(); this.data = data; this.next=null; } public ListNode(int data, ListNode next) { super(); this.data = data; this.next = next; } public void setData(int data) { this.data = data; } public ListNode getNext() { return next; } public void setNext(ListNode next) { this.next = next; } }
private Node ReverseList(Node current, Node previous) { if (current == null) return null; Node originalNext = current.next; current.next = previous; if (originalNext == null) return current; return ReverseList(originalNext, current); }
//this function reverses the linked list public Node reverseList(Node p) { if(head == null){ return null; } //make the last node as head if(p.next == null){ head.next = null; head = p; return p; } //traverse to the last node, then reverse the pointers by assigning the 2nd last node to last node and so on.. return reverseList(p.next).next = p; }
PointZeroTwo已经得到了优雅的答案和在Java相同…
public void reverseList(){ if(head!=null){ head = reverseListNodes(null , head); } } private Node reverseListNodes(Node parent , Node child ){ Node next = child.next; child.next = parent; return (next==null)?child:reverseListNodes(child, next); }
这就是我们如何在Opal中这样做的 – 一种纯粹的函数式编程语言。 而且，恕我直言 – 这样做recursion只有在这种情况下才有意义。
List Reverse(List l) { if (IsEmpty(l) || Size(l) == 1) return l; return reverse(rest(l))::first(l); }
rest（l）返回一个没有它的第一个节点的原始列表。 首先（l）返回第一个元素。 ::是一个连接运算符。
//Recursive solution class SLL { int data; SLL next; } SLL reverse(SLL head) { //base case - 0 or 1 elements if(head == null || head.next == null) return head; SLL temp = reverse(head.next); head.next.next = head; head.next = null; return temp; }
受到讨论recursion数据结构的不可变实现的文章的启发，我使用Swift将替代解决scheme放在一起。
领先的答案文件解决scheme突出了以下主题：
- 什么是空（空列表）的反向？
- 这里没关系，因为我们在Swift中没有保护。
- 什么是一个元素列表的相反？
- 元素本身
- 什么是一个n元素列表的相反？
- 第二个元素跟在第一个元素后面。
我已经在下面的解决scheme适用的地方调用了这些。
/** Node is a class that stores an arbitrary value of generic type T and a pointer to another Node of the same time. This is a recursive data structure representative of a member of a unidirectional linked list. */ public class Node<T> { public let value: T public let next: Node<T>? public init(value: T, next: Node<T>?) { self.value = value self.next = next } public func reversedList() -> Node<T> { if let next = self.next { // 3. The reverse of the second element on followed by the first element. return next.reversedList() + value } else { // 2. Reverse of a one element list is itself return self } } } /** @return Returns a newly created Node consisting of the lhs list appended with rhs value. */ public func +<T>(lhs: Node<T>, rhs: T) -> Node<T> { let tail: Node<T>? if let next = lhs.next { // The new tail is created recursively, as long as there is a next node. tail = next + rhs } else { // If there is not a next node, create a new tail node to append tail = Node<T>(value: rhs, next: nil) } // Return a newly created Node consisting of the lhs list appended with rhs value. return Node<T>(value: lhs.value, next: tail) }
使用recursion来反转链接列表。 这个想法是通过反转链接来调整链接。
public ListNode reverseR(ListNode p) { //Base condition, Once you reach the last node,return p if (p == null || p.next == null) { return p; } //Go on making the recursive call till reach the last node,now head points to the last node ListNode head = reverseR(p.next); //Head points to the last node //Here, p points to the last but one node(previous node), q points to the last node. Then next next step is to adjust the links ListNode q = p.next; //Last node link points to the P (last but one node) q.next = p; //Set the last but node (previous node) next to null p.next = null; return head; //Head points to the last node }
public void reverseLinkedList(Node node){ if(node==null){ return; } reverseLinkedList(node.next); Node temp = node.next; node.next=node.prev; node.prev=temp; return; }
public void reverse(){ if(isEmpty()){ return; } Node<T> revHead = new Node<T>(); this.reverse(head.next, revHead); this.head = revHead; } private Node<T> reverse(Node<T> node, Node<T> revHead){ if(node.next == null){ revHead.next = node; return node; } Node<T> reverse = this.reverse(node.next, revHead); reverse.next = node; node.next = null; return node; }
