Concept explainers
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...
Want to see the full answer?
Check out a sample textbook solutionChapter 20 Solutions
Starting Out with Java: From Control Structures through Data Structures (3rd Edition)
- Please explain Q# 1, A list operation that produces one summary item result is called Group of answer choices A. Map B. Fold C. Filter D. Iterate Q#2, What is an accumulator? Group of answer choices A. An optional argument to a helper method B. An argument to a recursive method tracks information over the course of the recursion C. None of the above D. A recursive method that returns an accumulated valuearrow_forward7 4 2 4 2 Tree #1 1 5 Tree #2 6 3 6 8 8 9 5 7 9 1 For parts a through g, implement the given method and demonstrate the method working with the two trees provided earlier. All code implemented in this assignment should be in a class called Homework 6. You may use the data structures and algorithm code from the lecture notes. Hint: Consider using recursion. To do so implement a private helper method that takes a Node and then recursively calls itself to traverse the tree. The public method would call the private method passing the tree's root as the Node.arrow_forwardConsider a scenario in which you would use recursive binary search. What would you do? What is the halting condition for a recursive binary search in the first place?arrow_forward
- public int numdescendantsmod(int y) without recursion. this m O ethod should return the number of nodes that have a value tha Remove t is 0 mod y.arrow_forwardAdd a recursive function to BST called avgCompares() that computes the average number of comparisons required by a random search hit in a particular BST (the internal path length of the tree divided by its size plus one). Create two implementations: a recursive approach (which requires linear time and space proportionate to the height) and a way similar to size() that adds a field to each node in the tree (which requires linear space and constant time each query).arrow_forwardGiven a singly linked list, print reverse of it using a recursive function printLinkedList( node *first ) where first is the pointer pointing to the first data node. For example, if the given linked list is 1->2->3->4, then output should be: 4 3 2 1 (note the whitespace in between each data value)arrow_forward
- do it with data structures - java Write a recursive private method called countLeafAndOneEvenChild to be included in class BinaryTree as discussed in the lectures. The method counts and returns the number of leaf nodes and nodes having only one even child node in the binary tree. This method is called from a public method countLeafAndOneEvenChild, given as follows: public int countLeafAndOneEvenChildBT() { return countLeafAndOneEvenChild(root); } Method heading: private int countLeafAndOneEvenChild (Node<E> node)arrow_forwardWritten in Dr Racket: Write a recursive function that takes a list of numbers as input and returns a list of the numbers in ascending order.Use the quicksort algorithmUse ( 20 13 74 5 12 9 22 95 22 6 101 72 3 53 33 21 96) as input. To do that, calculate the average value of a sublist before dividing it.(quicksort ‘( 20 13 74 5 12 9 22 95 22 6 101 72 3 53 33 21 96))returns ‘(3 5 6 9 12 13 20 21 22 22 33 53 72 74 95 96 101) Do not use sort, quicksort, set!, or mean.arrow_forwardWrite a recursive implementation of Euclid's Algorith for finding the greatest common divisor(GCD) of two intergers. Descriptions of this algorithm are available in algebra books and on theweb. (Note: A nonrecursive version of the GCD problem was given in the programming exercisesfor Chapter 7.) Write a test program that calls your GCD procedure five times, using thefollowing pairs of integers: (5,20),(24,18),(11,7),(432,226),(26,13). After each procedure call,display the GCD.arrow_forward
- Need help with trying to rewrite the getFrequencyOf method using recursion. I will provide the original non recursive code also. Try not to use the toArray method and use node chain. Non-recursive method public int getFrequencyOf(T anEntry) {int frequency = 0;int counter = 0;Node currentNode = firstNode;while ((counter < numberOfEntries) && (currentNode != null)) {if (anEntry.equals(currentNode.data)) {frequency++;}counter++;currentNode = currentNode.next;} return frequency;}arrow_forwardThe for construct is a recursive procedure that operates on a given list. Thus, it works so long as there are objects to process. Is this a genuine or untrue claim?arrow_forwardWrite a recursive private method called countDegree to be included in class BinaryTree as discussed in the lectures. If a node is having two child nodes, then its degree is two, if it is having one child node, its degree is one and leaf nodes have degree 0. The method counts and returns the total degree of all the nodes in the binary tree. Example: If a binary tree is having 9 nodes such that 3 nodes, each have 2 child nodes, 2 nodes each have only one child and there are 4 leaf nodes. So, the total degree of the binary tree = 3x2 + 2x1 + 0 = 8. This method is called from a public method countDegreeBT, given as follows: public int countDegreeBT() { return countDegree(root); } Method heading: private int countDegree(Node<E> node)arrow_forward
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning