Recursion - Reverse LinkedList with void function return type

Question

I tried to flip a linked list using recursion. I got a solution, but I can’t get it to work as described below on the Internet.

Flip the linked list using recursion, but the function should have an empty return type.

I managed to implement a function with a return type of Node . Below is my decision.

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

I can not imagine whether such a solution to this problem.

Any suggestions?

Answer 1

Tested, it works (provided that you have your own implementation of a linked list with Node , who know the 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; } } 

You call it with

 reverse(null, startNode); 

Answer 2

 public void recursiveDisplay(Link current){ if(current== null) return ; recursiveDisplay(current.next); current.display(); } 

Answer 3

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

Answer 4

This should work

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

although for efficiency with LinkedList it needs to be reorganized to use ListIterator

Answer 5

I am not familiar with Java, but here is the C ++ version. After changing the list, the list of headers is still preserved, which means that the list can be accessed from the old chapter 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; } 

Answer 6

Try this code instead - it really works

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

Answer 7

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

When calling the function, assign the return value as shown below:

  list.head=recurse2(list.head); 

Answer 8

The function below is based on the selected answer from darijan, all I did was add 2 lines of code so that it matches the code that you guys want to work:

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

In addition, I changed it to a non-stationary function, so the way to use it is: myLinkedList.reverse(null, myLinkedList.head);

Answer 9

Here is my version - void ReverseWithRecursion (Node currentNode) - This is a method of the LinkListDemo class, accessible to the head

• Basic example. If Node is null, then do nothing and return. If Node → Next is null, "Make It Head" and return.

• Another thing is the converse of the Next 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; } 

You call it this:

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

Answer 10

The easiest way I can imagine:

 public static <T> void reverse( LinkedList<T> list ) { if (list.size() <= 1) { return; } T first = list.removeFirst(); reverse( list); list.addLast( first ); }