Chapter 20, Problem 3AW

Explanation of Solution

Method definition for “reverse()”:

The recursive method definition for “reverse()” is given below:

/* Recursive method definition for "reverse" with parameter */

private Node reverse(Node list)

{

    //Create a node "newList"

    Node newList;

/* If the given node is null or last node is null, then */

    if((list == null) || (list.next == null))

    {

        /* Return the node */

        return list;

    }

/* Recursively call the method "reverse" for remaining node */

    newList = reverse(list.next);

    //Modify references for middle sequence

    list.next.next = list;

    list.next = null;

    //Return new head node in each recursion

    return newList;

}

/* Recursive Method definition for reverse method without parameter */

private void reverse()

{

    /* Call the method "reverse" with list head */

    first = reverse(first);

}

Explanation:

The above method definition is used to reverse the elements in a list.

• Recursive method definition of “reverse()” with an parameter “list”.
  • Create a node “newList”.
  • If the given node is null or last node is null, then return the node.
  • Recursively call the method “reverse” for remaining node.
  • Modify references for middle sequence.
  • Finally, return new head node in each recursion.
• Recursive method definition of “reverse()” without parameter.
  • Call the method “reverse” with list head.

Complete code:

The complete executable code for reverse the elements in a list using recursive “reverse()” method is given below:

//Define "LinkedList1" class

class LinkedList1

{

/** The code for this part is same as the textbook of "LinkedList1" class */  

/* Recursive method definition for "reverse" with parameter */

    private Node reverse(Node list)

    {

        //Create a node "newList"

        Node newList;

/* If the given node is null or last node is null, then */

        if((list == null) || (list.next == null))

        {

            /* Return the node */

            return list;

        }

/* Recursively call the method "reverse" for remaining node */

        newList = reverse(list...