CODEWITHSUNDEEP
javalinked-list
ilaunchpad
ilaunchpad

Reputation: 1313

LinkedList Recursion

public class LinkedList {

    Node head = null;
    int nodeCount= 0;
    int counter = 0;

    LinkedList() {
        head = null;
    }

   public Node reverseTest(Node L) {
       if(L == null || L.next ==null) {
           return L;
       }

       Node remainingNode =  reverseTest(L.next);
       Node cur = remainingNode;
       while(cur.next !=null) {
           cur=cur.next;
       }

       L.next = null;
       cur.next = L;

       return  remainingNode;
   }
}

public class LinkedListDemo {

    public static void main(String[] args) {

        LinkedList FriendList = new LinkedList();
        FriendList.insertNode("First");
        FriendList.insertNode("Second");
        FriendList.insertNode("Third");
        FriendList.insertNode("Fourth");

        FriendList.reverseTest(FriendList.head);
        // FriendList.copyObject(FriendList.head);
        String NameList = FriendList.toString();
        System.out.println(NameList);
        System.out.println("Finish");

    }
}

Confusion:

In the reverseTest method which is recursive after returning first L value from this line

if(L == null || L.next ==null) {
    return L;
}

we pass the value to remainingNode in this line

Node remainingNode =  reverseTest(L.next);

then we copy it to cur variable

 Node cur = remainingNode;

when we reach the line 

cur.next = L;

it updates the cur.next with L, but it also updates

remainingNode.next = L

I don't understand. How? Can someone point me what should I look into?

Upvotes: 0

Views: 92

Answers (3)

Joop Eggen
Joop Eggen

Reputation: 109623

Fist the head node will be changed by the reversal, so it is an in-out parameter. In java: in-parameter + result:

friendList.head = FriendList.reverseTest(FriendList.head);

The shown code loops/recurses much. The reason being that the recursion is done on the rest, and then the first element appended at the tail. Quite unnatural, circumstantial.

For a recursive solution, one should go a more natural solution. For such recursive solutions, an extra parameter helps. Here we have a to-do-list and a done-list as parameters.

Now you can delay, use "future" results:

public Node reverseTest(Node L) {
      return reverseRecursively(L, null);
}

private Node reverseRecursively(Node node, Node reversed) {
      if (node == null) {
          return reversed;
      }
      Node next = node.next;
      node.next = reversed;
      reversed = node;
      return reverseRecursively(next, reversed);
}

Here node will be the sublist of to-dos, and reversed the partial result of already reversed nodes.

This is called tail-recursion as there is a single recursive call at the end. So it can easily be written iteratively as a single loop.

Upvotes: 0

Falco
Falco

Reputation: 20

cur and remaining node are pointing to the same memory address. whatever you do to one will affect the other. You want them to point to two different memory locations.

Upvotes: 1

shruti1810
shruti1810

Reputation: 4047

There is a while loop in between Node cur = remainingNode; and cur.next = L:

while(cur.next !=null){
    cur=cur.next;
}

Hence, cur and remainingNode are not pointing to the same node. cur is now pointing to the last node of the list starting from remainingNode.

Upvotes: 0

Related Questions