Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.
Example
references the list
Manipulate the pointers of each node in place and return , now referencing the head of the list .
Function Description
Complete the reverse function in the editor below.
reverse has the following parameter:
SinglyLinkedListNode pointer head: a reference to the head of a list
Returns
SinglyLinkedListNode pointer: a reference to the head of the reversed list
Input Format
The first line contains an integer , the number of test cases.
Each test case has the following format:
The first line contains an integer , the number of elements in the linked list.
Each of the next lines contains an integer, the values of the elements in the linked list.
Constraints
, where is the element in the list.
Sample Input
1
5
1
2
3
4
5
Sample Output
5 4 3 2 1
Solution :
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
}
class SinglyLinkedListPrintHelper {
public static void printList(SinglyLinkedListNode node, String sep, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));
node = node.next;
if (node != null) {
bufferedWriter.write(sep);
}
}
}
}
class Result {
/*
* Complete the 'reverse' function below.
*
* The function is expected to return an INTEGER_SINGLY_LINKED_LIST.
* The function accepts INTEGER_SINGLY_LINKED_LIST llist as parameter.
*/
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode next;
* }
*
*/
public static SinglyLinkedListNode reverse(SinglyLinkedListNode llist) {
// Write your code here
SinglyLinkedListNode previous=null;
SinglyLinkedListNode current=llist;
SinglyLinkedListNode next=null;
while(current !=null)
{
next= current.next;
current.next=previous;
previous=current;
current=next;
}
return previous;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int tests = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, tests).forEach(testsItr -> {
try {
SinglyLinkedList llist = new SinglyLinkedList();
int llistCount = Integer.parseInt(bufferedReader.readLine().trim());
IntStream.range(0, llistCount).forEach(i -> {
try {
int llistItem = Integer.parseInt(bufferedReader.readLine().trim());
llist.insertNode(llistItem);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
SinglyLinkedListNode llist1 = Result.reverse(llist.head);
SinglyLinkedListPrintHelper.printList(llist1, " ", bufferedWriter);
bufferedWriter.newLine();
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
bufferedReader.close();
bufferedWriter.close();
}
}
Comments
Post a Comment