Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything.
Example
head* refers to the linked list with data values
1 -> 2 -> 3 -> NULL
Print the following:
3
2
1
Function Description
Complete the reversePrint function in the editor below.
reversePrint has the following parameters:
- SinglyLinkedListNode pointer head: a reference to the head of the list
Prints
The
values of each node in the reversed list.
Input Format
The first line of input contains t, the number of test cases.
The input of each test case is as follows:
- The first line contains an integer n, the number of elements in the list.
- Each of the next n lines contains a data element for a list node.
Constraints
1 <= n <= 1000
1 <= list[i] <= 1000, where list[i] is the i**th element in the list.
Sample Input
3
5
16
12
4
2
5
3
7
3
9
5
5
1
18
3
13
Sample Output
5
2
4
12
16
9
3
7
13
3
18
1
5
Explanation
There are three test cases. There are no blank lines between test case output.
The first linked list has 5 elements: 16 -> 12 -> 2 -> 4.Printing this in reverse order produces:5
2
4
12
16 The second linked list has 3 elements: 7 -> 3 -> 9 -> NULL. Printing this in reverse order produces: 9
3
7 The third linked list has 5 elements:
5 - > 1 -> 18 -> 3 -> NULL. Printing this in reverse order produces:
13
3
18
1
5
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <sdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
typedef struct SinglyLinkedListNode SinglyLinkedListNode;
typedef struct SinglyLinkedList SinglyLinkedList;
struct SinglyLinkedListNode {
int data;
SinglyLinkedListNode* next;
};
struct SinglyLinkedList {
SinglyLinkedListNode* head;
SinglyLinkedListNode* tail;
};
SinglyLinkedListNode* create_singly_linked_list_node(int node_data) {
SinglyLinkedListNode* node = malloc(sizeof(SinglyLinkedListNode));
node->data = node_data;
node->next = NULL;
return node;
}
void insert_node_into_singly_linked_list(SinglyLinkedList** singly_linked_list, int node_data) {
SinglyLinkedListNode* node = create_singly_linked_list_node(node_data);
if (!(*singly_linked_list)->head) {
(*singly_linked_list)->head = node;
} else {
(*singly_linked_list)->tail->next = node;
}
(*singly_linked_list)->tail = node;
}
void print_singly_linked_list(SinglyLinkedListNode* node, char* sep) {
while (node) {
printf("%d", node->data);
node = node->next;
if (node) {
printf("%s", sep);
}
}
}
void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;
free(temp);
}
}
/*
* Complete the 'reversePrint' function below.
*
* The function accepts INTEGER_SINGLY_LINKED_LIST llist as parameter.
*/
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode* next;
* };
*
*/
void reversePrint(SinglyLinkedListNode* head) {
if(head == NULL) return;
else{
reversePrint(head->next);
printf("%d\n",head->data);
}
}
int main()
{
char* tests_endptr;
char* tests_str = readline();
int tests = strtol(tests_str, &tests_endptr, 10);
if (tests_endptr == tests_str || *tests_endptr != '\0') { exit(EXIT_FAILURE); }
for (int tests_itr = 0; tests_itr < tests; tests_itr++) {
SinglyLinkedList* llist = malloc(sizeof(SinglyLinkedList)>;
llist->head = NULL;
llist->tail = NULL;
char* llist_count_endptr;
char* llist_count_str = readline();
int llist_count = strtol(llist_count_str, &llist_count_endptr, 10);
if (llist_count_endptr == llist_count_str || *llist_count_endptr != '\0') { exit(EXIT_FAILURE); }
for (int i = 0; i < llist_count; i++) {
char* llist_item_endptr;
char* llist_item_str = readline();
int llist_item = strtol(llist_item_str, &llist_item_endptr, 10);
if (llist_item_endptr == llist_item_str || *llist_item_endptr != '\0') { exit(EXIT_FAILURE); }
insert_node_into_singly_linked_list(&llist, llist_item);
}
reversePrint(llist->head);
}
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
class SinglyLinkedListNode {
public:
int data;
SinglyLinkedListNode *next;
SinglyLinkedListNode(int node_data) {
this->data = node_data;
this->next = nullptr;
}
};
class SinglyLinkedList {
public:
SinglyLinkedListNode *head;
SinglyLinkedListNode *tail;
SinglyLinkedList() {
this->head = nullptr;
this->tail = nullptr;
}
void insert_node(int node_data) {
SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
if (!this->head) {
this->head = node;
} else {
this->tail->next = node;
}
this->tail = node;
}
};
void print_singly_linked_list(SinglyLinkedListNode* node, string sep) {
while (node) {
cout << node->data;
node = node->next;
if (node) {
cout << sep;
}
}
}
/*
* Complete the 'reversePrint' function below.
*
* The function accepts INTEGER_SINGLY_LINKED_LIST llist as parameter.
*/
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode* next;
* };
*
*/
void reversePrint(SinglyLinkedListNode* head) {
if(head == NULL) {
return;
}
reversePrint(head->next);
cout << head->data << endl;
}
int main()
{
string tests_temp;
getline(cin, tests_temp);
int tests = stoi(ltrim(rtrim(tests_temp)));
for (int tests_itr = 0; tests_itr < tests; tests_itr++) {
SinglyLinkedList* llist = new SinglyLinkedList();
string llist_count_temp;
getline(cin, llist_count_temp);
int llist_count = stoi(ltrim(rtrim(llist_count_temp)));
for (int i = 0; i < llist_count; i++) {
string llist_item_temp;
getline(cin, llist_item_temp);
int llist_item = stoi(ltrim(rtrim(llist_item_temp))>;
llist->insert_node(llist_item);
}
reversePrint(llist->head);
}
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
s.end()
);
return s;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static 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;
}
}
public static void printSinglyLinkedList(SinglyLinkedListNode node, String sep) {
while (node != null) {
System.out.print(node.data);
node = node.next;
if (node != null) {
System.out.print(sep);
}
}
}
static void reversePrint(SinglyLinkedListNode head) {
if (head == null) return;
// print list of head node
reversePrint(head.next);
// After everything else is printed
System.out.println(head.data+" ");
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int tests = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int testsItr = 0; testsItr < tests; testsItr++) {
SinglyLinkedList llist = new SinglyLinkedList();
int llistCount = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
for (int i = 0; i < llistCount; i++) {
int llistItem = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");
llist.insertNode(llistItem);
}
reversePrint(llist.head);
}
scanner.close();
}
}
#4 Code Example with Javascript Programming
Code -
Javascript Programming
'use strict';
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
const SinglyLinkedListNode = class {
constructor(nodeData) {
this.data = nodeData;
this.next = null;
}
};
const SinglyLinkedList = class {
constructor() {
this.head = null;
this.tail = null;
}
insertNode(nodeData) {
const node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
};
function printSinglyLinkedList(node, sep) {
while (node != null) {
process.stdout.write(String(node.data));
node = node.next;
if (node != null) {
process.stdout.write(sep);
}
}
}
/*
* Complete the 'reversePrint' function below.
*
* The function accepts INTEGER_SINGLY_LINKED_LIST llist as parameter.
*/
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode next;
* }
*
*/
function reversePrint(head) {
if (head !== null) {
reversePrint(head.next);
console.log(head.data)
}
}
function main() {
const tests = parseInt(readLine(), 10);
for (let testsItr = 0; testsItr < tests; testsItr++) {
const llistCount = parseInt(readLine(), 10);
let llist = new SinglyLinkedList();
for (let i = 0; i < llistCount; i++) {
const llistItem = parseInt(readLine(), 10);
llist.insertNode(llistItem);
}
reversePrint(llist.head);
}
}