CODEWITHSUNDEEP
javaalgorithmdata-structuresrecursionlinked-list
tmgr
tmgr

Reputation: 1187

Recursion - Reverse LinkedList with void function return type

I was trying to reverse a linked list using recursion. I got the solution, but can't get it to work for below question found on internet.

Reverse a linked list using recursion but function should have void return type.

I was able to implement the function with return type as Node. Below is my solution.

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 cannot imagine if there will be such a solution to this problem.

Any suggestions ?

Upvotes: 4

Views: 5833

Answers (11)

Rishindra Sharma
Rishindra Sharma

Reputation: 1

Given that you have a Node class as below:

public class Node
{
    public int data;
    public Node next;
    public Node(int d)   //constructor.
    {
        data = d;
        next = null;
    }
}

And a linkedList class where you have declared a head node, so that it can be accessed by the methods that you create inside LinkedList class. The method 'ReverseLinkedList' takes a Node as an argument and reverses the ll.

You may do a dry run of the code by considering 1->2 as the linkedList. Where node = 1, node.next = 2.

 public class LinkedList
{
    public Node? head;  //head of list

    public LinkedList()
    {
        head = null;
    }


    public void ReverseLinkedList(Node node)
    {
        if(node==null)
        {
            return;
        }
        if(node.next==null)
        {
            head = node;
            return;
        }
        

        ReverseLinkedList(node.next);   // node.next = rest of the linkedList

        node.next.next = node;   // consider node as the first part of linkedList
        node.next = null;

    }

    
}

Upvotes: 0

Venu
Venu

Reputation: 17

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

Upvotes: 1

Ajay Parmar
Ajay Parmar

Reputation: 39

Here is my version - void ReverseWithRecursion(Node currentNode) - It is method of LinkListDemo Class so head is accessible

  1. Base Case - If Node is null, then do nothing and return. If Node->Next is null, "Make it head" and return.

  2. Other Case - Reverse the Next of 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 like 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);

Upvotes: 0

MrGuy
MrGuy

Reputation: 664

The function below is based on the chosen answer from darijan, all I did is adding 2 lines of code so that it'd fit in the code 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;
        }   
    }

Also, I've changed it to a non static function so then the way to use it would be: myLinkedList.reverse(null, myLinkedList.head);

Upvotes: 0

Siddhahast Mohapatra
Siddhahast Mohapatra

Reputation: 11

public void recursiveDisplay(Link current){

        if(current== null)
           return ;
        recursiveDisplay(current.next);
        current.display();
}

Upvotes: 1

algoguru
algoguru

Reputation: 1

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;

}

While calling the function assign the return value as below:

 list.head=recurse2(list.head);

Upvotes: 0

kellyfj
kellyfj

Reputation: 6983

Try this code instead - it actually 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;        
}

Upvotes: 0

eddyxu
eddyxu

Reputation: 668

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

Upvotes: 0

darijan
darijan

Reputation: 9795

Tested, it works (assuming you have your own implementation of a linked list with Nodes that 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);

Upvotes: 3

tibtof
tibtof

Reputation: 7967

The simplest method that I can think of it's:

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

Upvotes: -1

Evgeniy Dorofeev
Evgeniy Dorofeev

Reputation: 136162

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

though to be efficient with LinkedList it should be refactored to use ListIterator

Upvotes: 0

Related Questions