Solve in Java In this problem, you will write a method that reverses a linked list. Your algorithm must have a worst-case runtime in O(n) and a worst- case space complexity of O(1) beyond the input. For example, if our input is: 5 7 1 2 3 then we should print: 3 2 1 7 5
Solve in Java
In this problem, you will write a method that reverses a linked
list. Your
case space complexity of O(1) beyond the input.
For example, if our input is:
5 7 1 2 3
then we should print:
3 2 1 7 5
Running and testing:
If you click run, you may notice that your IDE seems to do nothing. Scan-
ner is waiting for an input so to test something, enter space-separated
numbers like:
3 5 1 2 5
and hit enter, a linked list will be created with those values, call your
reverse method, and print out the result.
Please note that the result code contains the following les:
Node: A class representing linked list nodes. Each node contains
an integer value, a variable next representing the next node in the
list (which is null if we're at the last node), and a variable
1
prev representing the previous node in the list (which is null if we're
at the rst node).
LinkedList: A class representing a stripped-down version of a linked
list. We keep track of the rst and last nodes of the list, and have
methods for creating linked lists from arrays and converting linked
lists to space-separated strings. Your task is to complete the
reverse() method in this class.
Main: A class with a main() method that collects input into a linked
list, calls the reverse() method, and outputs the resulting linked list.
Restrictions:
(a) In this problem, you must use the custom LinkedList class. You
may not use the normal LinkedList class.
(b) Your algorithm must have a worst-case runtime in O(n) and a worst-
case space complexity of O(1) beyond the input. The class Main should provide code for turning the input into a linked list and turning a linked list into the output string. Your job is to implement the reverse method() in the LinkedList class
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
