Question

In this problem, you will write a program that reverses a linked

list. Your program should take as input a space-separated list of integers

representing the original list, and output a space-separated list of integers

representing the reversed list. Your algorithm must have a worst-case run-

time 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

Please note that the starter code contains the following files:

• MyLinkedListNode: 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 prev

representing the previous node in the list (which is null if we’re at the first node). You will probably need to modify this file.

• MyLinkedList: A class representing a stripped-down version of a

linked list. We keep track of the first 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. You should not modify this file.

Restrictions:

(a) In this problem, you must use the custom MyLinkedList class. You may not use the normal LinkedList class. Any solutions that do not use MyLinkedList will receive a zero in all categories.

(b) Your algorithm must have a worst-case runtime in O(n) and a worst-

case space complexity of O (1) beyond the input. Any solutions that are less efficient will receive at most half credit for all categories. The class Main provides starter 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 MyLinkedList class. You will need to modify the MyLinkedListNode class as well.

Main.java

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
  
// Read in the list of numbers
int[] numbers;
String input = sc.nextLine();
if (input.equals("")) {
numbers = new int[0];
} else {
String[] numberStrings = input.split(" ");
numbers = new int[numberStrings.length];
for (int i = 0; i < numberStrings.length; i++) {
numbers[i] = Integer.parseInt(numberStrings[i]);
}
}
  
// Create a MyLinkedList containing these numbers
MyLinkedList numbersList = new MyLinkedList(numbers);
  
// Reverse the list
numbersList.reverse();
  
// Print the reversed list
System.out.println(numbersList.toString());
}
}

MyLinkedList.java

public class MyLinkedList {
private MyLinkedListNode firstNode = null;
private MyLinkedListNode lastNode = null;
private int length = 0;
  
/**
* Constructs a MyLinkedList from an integer array.
*/
public MyLinkedList(int[] numbersArray) {
// set length
length = numbersArray.length;
  
// leave the first and last nodes as null if there
// are no elements in the array
if (numbersArray.length == 0) {
return;
}
  
// set the first node to the first number
firstNode = new MyLinkedListNode(numbersArray[0], null, null);
if (numbersArray.length == 1) {
lastNode = firstNode;
return;
}
  
// create all the middle nodes
MyLinkedListNode prevNode = firstNode;
for (int i = 1; i < numbersArray.length - 1; i++) {
MyLinkedListNode currentNode =
new MyLinkedListNode(numbersArray[i], prevNode, null);
prevNode.setNext(currentNode);
prevNode = currentNode;
}
  
// set the last node to the last number
lastNode = new MyLinkedListNode(
numbersArray[numbersArray.length-1],
prevNode,
null);
prevNode.setNext(lastNode);
}
  
@Override
public String toString() {
StringBuilder sb = new StringBuilder(length);
  
MyLinkedListNode currentNode = firstNode;
for (int i = 0; i < length; i++) {
sb.append(currentNode.toString());
if (i < length - 1) {
sb.append(" ");
currentNode = currentNode.getNext();
}
}
  
return sb.toString();
}
  
/**
* Reverses this linked list.
*/
public void reverse() {
// TODO implement this
}
}

MyLinkedListNode.java

public class MyLinkedListNode {
private int value = 0;
private MyLinkedListNode prev = null;
private MyLinkedListNode next = null;
  
public MyLinkedListNode(int value, MyLinkedListNode prev, MyLinkedListNode next) {
this.value = value;
this.prev = prev;
this.next = next;
}
  
public MyLinkedListNode getNext() {
return next;
}
  
public void setNext(MyLinkedListNode next) {
this.next = next;
}
  
@Override
public String toString() {
return (new Integer(this.value)).toString();
}
}

Answer 1

public void reverse() {

//initialise the firstNode

MyLinkedListNode currentNode = firstNode;

//Initally next node is null

MyLinkedListNode next = null;

//Initally previous node is null

MyLinkedListNode prev = null;

//Iterate till node becomes null

while (currentNode != null) {

//Next node will point to next of current node

next = currentNode.getNext();

//Make the current node as previous node because we are reversing

currentNode.setNext(prev);

//Make previous as current

prev = currentNode;

//current becomes the next node

currentNode = next;

}

firstNode = prev;

}

=================================================

SEE OUTPUT

Thanks, PLEASE COMMENT if there is any concern.

==================