1. Write a code for reversing a singly linked list L using only a constant amoun
ID: 3902539 • Letter: 1
Question
1. Write a code for reversing a singly linked list L using only a constant amount of additional space and not using any recursion. What is the time complexity of your code? Write a recursive code that finds the number of values greater than x in a linked list of integers. Write a short recursive Java method that takes a character string s and outputs its reverse. So for example, the reverse of "pots&pans;" would be "snap&stop; 2. 3. 4. Let B be an array of size n 2 6 containing integers from 1 to n - 5, inclusive, with exactly five 5. 6. repeated. Describe a good algorithm for finding the five integers in B that are repeated Write a short recursive Java method that determines if a string s is a palindrome, that is, it is equal to its reverse. For example, "racecar" and "gohangasalamiimalasagnahog" are palindromes Write a code using recursion to add all the elements in a nxn (two dimensional) array of integers.Explanation / Answer
1) Answer
// Class ReverseSingleLinkedList definition
class ReverseSingleLinkedList
{
// Inner static class SingleNode definition
static class SingleNode
{
// Instance variable to store data
int value;
// Instance object to point to next node
SingleNode next;
// Parameterized constructor
SingleNode(int data)
{
value = data;
next = null;
}// End of parameterized constructor
}// End of inner class SingleNode
// Declares an object of the class SingleNode head object
static SingleNode head;
// Method to reverse the linked list
SingleNode reverse(SingleNode temp)
{
// Creates a node previous to point to previous node
SingleNode previous = null;
// Creates a node current to point to current node
SingleNode current = temp;
// Creates a node next to point to next node
SingleNode next = null;
// Loops till not null
while (current != null)
{
// Node next points to current node next
next = current.next;
// Current node next points to previous node
current.next = previous;
// Previous node points to current node
previous = current;
// Current node points to next node
current = next;
}// End of while loop
// Node temp points to previous node
temp = previous;
// Returns the temp node
return temp;
}// End of method
// Method to print content of single linked list
void printList(SingleNode temp)
{
// Loops till not null
while (temp != null)
{
// Displays the current node value
System.out.print(temp.value + " ");
// Move next
temp = temp.next;
}// End of while loop
}// End of method
// main method definition
public static void main(String[] s)
{
// Creates an object of class ReverseSingleLinkedList
ReverseSingleLinkedList list = new ReverseSingleLinkedList();
// Creates a node and adds it to linked list
list.head = new SingleNode(15);
list.head.next = new SingleNode(25);
list.head.next.next = new SingleNode(35);
list.head.next.next.next = new SingleNode(45);
System.out.print(" Original Single Linked List Order: ");
// Calls the method to displays original order
list.printList(head);
// Calls the method to reverse the list
head = list.reverse(head);
System.out.println();
System.out.print(" Reversed Single Linked List: ");
// Calls the method to displays reverse order
list.printList(head);
}// End of main method
}// End of class
Sample Output:
Original Single Linked List Order: 15 25 35 45
Reversed Single Linked List: 45 35 25 15
2) Answer
package recursion;
// Class MyNode Definition
class MyNode
{
// Instance variable to store data
int value;
// Instance object to point to next node
MyNode next;
// Parameterized constructor
MyNode(int data)
{
value = data;
next = null;
}// End of parameterized constructor
}// End of class
// Class CountGreaterThanXLinkedList definition
public class CountGreaterThanXLinkedList
{
// Declares a head node
MyNode head;
// Method to inserts a new Node at front of the list.
public void insertNode(int newData)
{
// Creates a new node using parameterized constructor
MyNode newNode = new MyNode(newData);
// Make next of new Node as head
newNode.next = head;
// Move the head to point to new Node
head = newNode;
}// End of method
// Recursive method to returns count of nodes in linked list having value greater than x
public int getCountRec(MyNode currentNode, int x, int count)
{
// Checks if currentNode is null then return count
if (currentNode == null)
return count;
// Checks if the current node value is greater than x then increase the counter
if(currentNode.value > x)
count++;
// Count is this node plus rest of the list
return getCountRec(currentNode.next, x, count);
}// End of method
// Main method to call recursive method to count number of numbers greater than x
public int getCount(int x)
{
// Calls the method to count and returns the count
return getCountRec(head, x, 0);
}// End of method
// main method definition
public static void main(String[] s)
{
// Creates an object of the class CountGreaterThanXLinkedList
CountGreaterThanXLinkedList myLlist = new CountGreaterThanXLinkedList();
myLlist.insertNode(10);
myLlist.insertNode(20);
myLlist.insertNode(30);
myLlist.insertNode(40);
myLlist.insertNode(50);
myLlist.insertNode(60);
// Calls the method to count and displays the number of items greater than 20
System.out.println("Count of nodes is " + myLlist.getCount(20));
}// End of main method
}// End of class
Sample Output:
Count of nodes is 4
3) Answer
import java.util.Scanner;
// Class ReverseString definition
class ReverseString
{
// Static method to print reverse of the string passed as parameter
static void reverseString(String str)
{
// Checks if string is null or string length is less than or equals to one
// Displays the original string
if ((str == null) || (str.length() <= 1))
System.out.println(str);
// Otherwise
else
{
// Displays length minus one character
System.out.print(str.charAt(str.length()-1));
// Recursively calls the function with length minus on as second parameter
reverseString(str.substring(0, str.length() -1));
}// End of else
}// End of method
// main function definition
public static void main(String[] s)
{
// Scanner class object created
Scanner sc = new Scanner(System.in);
System.out.print(" Enter the String to print reverse: ");
String string = sc.nextLine();
System.out.print(" Reverse: ");
// Calls the function to display the string in reverse order
reverseString(string);
}// End of main method
}// End of class
Sample Output:
Enter the String to print reverse: Check this
Reverse: siht kcehC
5) Answer
import java.util.Scanner;
// Class Palindrome definition
class Palindrome
{
// Recursive method to check palindrome
public static boolean isPalindrome(String str)
{
// Checks if length is 0 or 1 then return true for the String is palindrome
if(str.length() == 0 || str.length() == 1)
return true;
/* Otherwise check for first and last char of String:
* If they are same then do the same thing for a substring
* with first and last char removed, and carry on this
* until you string completes or condition fails by calling itself(Recursion)
*/
if(str.charAt(0) == str.charAt(str.length()-1))
return isPalindrome(str.substring(1, str.length()-1));
/* If program control reaches to this statement it means
* the String is not palindrome hence return false.
*/
return false;
}// End of method
// main method definition
public static void main(String[]s)
{
// Scanner class object created
Scanner sc = new Scanner(System.in);
System.out.print(" Enter the String to check palindrome: ");
String string = sc.nextLine();
// Call the function to check if function returns true then the string is palindrome else not
if(isPalindrome(string))
System.out.println(string + " is a palindrome.");
else
System.out.println(string + " is not a palindrome.");
// Close the scanner class
sc.close();
}// End of main method
}// End of class
Sample Output 1:
Enter the String to check palindrome: madam
madam is a palindrome.
Sample Output 2:
Enter the String to check palindrome: this
this is not a palindrome.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.