реверсивный связанный список в java

<p>я некоторое время работал над проектом java для класса. это реализация связанного списка (здесь он называется <code>addresslist</code>, содержащий простые узлы, называемые <code>listnode</code>). суть в том, что все должно быть сделано с помощью рекурсивных алгоритмов. я был в состоянии сделать все отлично без одного метода: <code>public addresslist reverse()</code> </p><p>listnode: </p><pre><code>public class listnode{ public string data; public listnode next; } </code></pre><p>прямо сейчас моя функция <code>reverse</code> просто вызывает вспомогательную функцию, которая принимает аргумент для разрешения рекурсии.</p><pre><code>public addresslist reverse(){ return new addresslist(this.reverse(this.head)); } </code></pre><p>с моей вспомогательной функцией, имеющей подпись <code>private listnode reverse(listnode current)</code>.</p><p>на данный момент у меня это работает итеративно с использованием стека, но это не то, что требует спецификация. я нашел алгоритм в c, который рекурсивно обращал и преобразовывал его в java-код вручную, и он работал, но я не понимал его.</p><p>правка: неважно, я понял это в то же время.</p><pre><code>private addresslist reverse(listnode current, addresslist reversedlist){ if(current == null) return reversedlist; reversedlist.addtofront(current.getdata()); return this.reverse(current.getnext(), reversedlist); } </code></pre><p>пока я здесь, кто-нибудь видит проблемы с этим маршрутом?</p>

<p>в одном ответе есть код, который объясняет его, но вам, возможно, будет легче начать снизу вверх, задавая и отвечая на крошечные вопросы (таков подход в «маленьком лиспере»):</p><ol> <li>что является противоположностью нуля (пустой список)? ноль.</li> <li>что является обратным списку из одного элемента? элемент.</li> <li>что является противоположностью n списка элементов? обратная сторона остальной части списка, за которой следует первый элемент.</li> </ol><hr><pre><code>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; } </code></pre>

<p>мне задали этот вопрос на собеседовании, и меня раздражало, что я возился с ним, так как немного нервничал.</p><p>это должно перевернуть односвязный список, вызываемый с помощью reverse (head, null); , так что если бы это был ваш список:</p><pre>1-> 2-> 3-> 4-> 5-> null он станет: 5-> 4-> 3-> 2-> 1-> null</pre><pre><code> //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 } </code></pre><p>правка: я сделал как 6 правок, показывая, что это все еще немного сложно для меня лол</p>

<p>я прошел половину пути (до нуля и один узел, как предложено плинтусом), но потерял трек после выполнения рекурсивного вызова. однако, после прочтения поста плинтусом, вот что я придумал:</p><pre><code>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; } </code></pre>

<p>вот еще одно рекурсивное решение. у него меньше кода внутри рекурсивной функции, чем у некоторых, поэтому он может быть немного быстрее. это c #, но я считаю, что java будет очень похожа.</p><pre><code>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); } } </code></pre>

<p>алго должен будет работать на следующей модели,</p><ul> <li>следить за головой</li> <li>рекурс до конца списка ссылок</li> <li>обратная связь</li> </ul><p>состав:</p><pre><code>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></pre><p>код:</p><pre><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; } </code></pre><p>результат:</p><pre><code>head-->12345 head-->54321 </code></pre>

<p>я думаю, что это более чистое решение, которое напоминает lisp</p><pre><code>// 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; } </code></pre>

<p>я знаю, что это старый пост, но большинство ответов не являются хвостовыми рекурсивными, то есть они выполняют некоторые операции после возврата из рекурсивного вызова, и, следовательно, не являются наиболее эффективными.</p><p>вот хвостовая рекурсивная версия:</p><pre><code>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. } </code></pre><p>звоните с:</p><pre><code>node newhead = reverse(head, head.getnext()); </code></pre>

<pre><code>public node reverselistrecursive(node curr) { if(curr == null){//base case return head; } else{ (reverselistrecursive(curr.next)).next = (curr); } return curr; } </code></pre>

<pre> void reverse (node1, node2) { if (node1.next! = null) обратное (node1.next, node1); node1.next = node2; } вызывать этот метод как обратный (start, null); </pre>

<pre><code>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); } </code></pre>

<p>обратное с помощью рекурсивного алгоритма.</p><pre><code>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; } </code></pre><p>итеративным</p><pre><code>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; } </code></pre>

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

<p>вот простой итеративный подход:</p><pre><code>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; } </code></pre><p>и вот рекурсивный подход: </p><pre><code>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; } </code></pre>

<p>это решение демонстрирует, что аргументы не требуются.</p><pre><code>/** * 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 } </code></pre><p>вот вспомогательный код, чтобы продемонстрировать, что это работает:</p><pre><code>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()); } } </code></pre>

<p>pointzerotwo получил элегантный ответ и то же самое в java ...</p><pre><code>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); } </code></pre>

<p>поскольку java всегда передается по значению, для рекурсивного обращения связанного списка в java обязательно верните «новый заголовок» (головной узел после реверсии) в конце рекурсии. </p><pre><code>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; } </code></pre>

<p>вдохновленный <a href="https://www.google.com/search?q=avl%20swift&oq=avl%20swift&aqs=chrome..69i57j69i60l5.1086j0j4&sourceid=chrome&es\_sm=119&ie=utf-8">статьей</a> обсуждая неизменные реализации рекурсивных структур данных, я собрал альтернативное решение, используя swift.</p><p>ведущее решение для ответов на документы, выделив следующие темы:</p><ol> <li>что является противоположностью нуля (пустой список)? <ul> <li>здесь не важно, потому что у нас в свифте нулевая защита.</li> </ul></li> <li>что является обратным списку из одного элемента? <ul> <li>сам элемент</li> </ul></li> <li>что является обратным списку n элементов? <ul> <li>реверс второго элемента, за которым следует первый элемент.</li> </ul></li> </ol><p>я назвал их, где это применимо, в приведенном ниже решении.</p><pre><code>/** 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) } </code></pre>

<p>реверсирование связанного списка с использованием рекурсии. идея заключается в корректировке ссылок путем их изменения.</p><pre><code> 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 } </code></pre>

<pre><code>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); } } </code></pre><p>вызов с использованием: head = reverserec (null, head);</p>

<pre><code>public void reverselinkedlist(node node){ if(node==null){ return; } reverselinkedlist(node.next); node temp = node.next; node.next=node.prev; node.prev=temp; return; } </code></pre>

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

<p>решение: </p><pre><code>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); } </code></pre><p>}</p>

<pre><code>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. } </code></pre>

<pre><code>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); } </code></pre>

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

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

<p>то, что сделали другие ребята, в другом посте - игра с контентом, то, что я сделал, - это игра по связанному списку, она переворачивает участника связанного списка, а не по значению членов.</p><pre><code>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 ); } </code></pre>

<pre><code>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+" "); } } } </code></pre>