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 19 Solutions
Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
- Implement a recursive version of the size method for SinglyLinkedLists. (Hint: A wrapper may be useful.)arrow_forwardPlease 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_forward
- Implement the inordermethod in BST using a stack instead of recursion. Write a test program thatprompts the user to enter 15 integers, stores them in a BST, and invokes theinorder method to display the elements.arrow_forwardpublic 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_forwarddo 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_forward
- Java Programming language Please help me with this. Thanks in advance.arrow_forwardNeed 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_forwardCreate a recursive method isOrdered() that takes a Node as an argument and two keys min and max as arguments and returns true if all the keys in the tree are between min and max; min and max are indeed the smallest and largest keys in the tree, respectively; and the BST ordering property holds for all keys in the tree; false otherwise.arrow_forward
- Write 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_forwardThe purpose of this assignment is to practice using Recursion with backtracking to solve a maze. I need help to implement the private static void solve(Maze maze, Coordinate currentPos, ArrayList<Coordinate> path, ArrayList<Coordinate> history) method in the MazeSolver class.arrow_forwardA consecutive sequence a list of numbers that are organized in increasing order with the next eleme. one bigger than the current. Write a non-recursive method "lengthConsec", which takes an IntNode myList as the parameter and returns the length of the consecutive sequence in myList. To simplify the implementation, you can assume that there is no more than one consecutive sequence in the list. For example, in the following linked list, the consecutive sequence begins at node "5" and ends at node "7", so lengthConsec (myList) should return 3 in this case. myList 8 13 4 public class IntNode { 12 private int m_data; private IntNode m_link; Consecutive sequence 6 7 28arrow_forward
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning