## Algorithm

Problem Name: Data Structures - Reverse a linked list

In this HackerRank in Data Structures - Reverse a linked list solutions

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

head references the list 1 -> 2 -> 3 -> NULL

Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3 -> 2 -> 1 -> NULL

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 t, the number of test cases.

Each test case has the following format:

The first line contains an integer n, the number of elements in the linked list.
Each of the next n lines contains an integer, the data values of the elements in the linked list.

Constraints

• 1 <= t <= 10
• 1 <= n <= 1000
• 1 <= list[i] <= 1000, where list[i] is the i**th element in the list.

Sample Input

``````1
5
1
2
3
4
5
``````

Sample Output

``````5 4 3 2 1
``````

Explanation

The initial linked list is: 1 -> 2 -> 3 -> 4 -> 5 -> NULL.

The reversed linked list is: 5 -> 4- > 3 -> 2 -> 1 -> NULL.

## 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 <stdint.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, FILE* fptr) {
while (node) {
fprintf(fptr, "%d", node->data);

node = node->next;

if (node) {
fprintf(fptr, "%s", sep);
}
}
}

void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;

free(temp);
}
}

/*
* 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;
* };
*
*/

SinglyLinkedListNode* reverse(SinglyLinkedListNode* head) {
if (head == NULL) return NULL;
if (head->next == NULL) {
return head;
} else {
SinglyLinkedListNode *newHead = reverse(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}

}

int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

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);
}

SinglyLinkedListNode* llist1 = reverse(llist->head);

char *sep = " ";

print_singly_linked_list(llist1, sep, fptr);
fprintf(fptr, "\n");

free_singly_linked_list(llist1);
}

fclose(fptr);

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;
}

``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

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, ofstream& fout) {
while (node) {
fout << node->data;

node = node->next;

if (node) {
fout << sep;
}
}
}

void free_singly_linked_list(SinglyLinkedListNode* node) {
while (node) {
SinglyLinkedListNode* temp = node;
node = node->next;

free(temp);
}
}

SinglyLinkedListNode* reverse(SinglyLinkedListNode* head) {
SinglyLinkedListNode*rHead =NULL;
while(head != NULL){
SinglyLinkedListNode* node = new SinglyLinkedListNode(head->data);
node->next = rHead;
rHead = node;

head = head->next;
}
return rHead;
}

int main()
{
ofstream fout(getenv("OUTPUT_PATH"));

int tests;
cin >> tests;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int tests_itr = 0; tests_itr  <  tests; tests_itr++) {
SinglyLinkedList* llist = new SinglyLinkedList();

int llist_count;
cin >> llist_count;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

for (int i = 0; i  <  llist_count; i++) {
int llist_item;
cin >> llist_item;
cin.ignore(numeric_limits < streamsize>::max(), '\n');

llist->insert_node(llist_item);
}

SinglyLinkedListNode* llist1 = reverse(llist->head);

print_singly_linked_list(llist1, " ", fout);
fout << "\n";

free_singly_linked_list(llist1);
}

fout.close();

return 0;
}
``````
Copy The Code &

### #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, BufferedWriter bufferedWriter) throws IOException {
while (node != null) {
bufferedWriter.write(String.valueOf(node.data));

node = node.next;

if (node != null) {
bufferedWriter.write(sep);
}
}
}

static SinglyLinkedListNode reverse(SinglyLinkedListNode head) {
SinglyLinkedListNode t = head;
Stack < Integer> x = new Stack<>();
while(t != null){
x.push(t.data);
t = t.next;
}
t = head;
while(t != null){
t.data = x.pop();
t = t.next;
}
return head;
}
private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

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);
}

SinglyLinkedListNode llist1 = reverse(llist.head);

printSinglyLinkedList(llist1, " ", bufferedWriter);
bufferedWriter.newLine();
}

bufferedWriter.close();

scanner.close();
}
}
``````
Copy The Code &

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import math
import os
import random
import re
import sys

class SinglyLinkedListNode:
def __init__(self, node_data):
self.data = node_data
self.next = None

class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None

def insert_node(self, node_data):
node = SinglyLinkedListNode(node_data)

if not self.head:
self.head = node
else:
self.tail.next = node

self.tail = node

def print_singly_linked_list(node, sep, fptr):
while node:
fptr.write(str(node.data))

node = node.next

if node:
fptr.write(sep)

#
# 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
#
#

def reverse(head):
nxt = None
while head:
tmp = head.next
head.next = nxt
nxt = head
head = tmp
return nxt

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

tests = int(input())

for tests_itr in range(tests):
llist_count = int(input())

llist = SinglyLinkedList()

for _ in range(llist_count):
llist_item = int(input())
llist.insert_node(llist_item)

llist1 = reverse(llist.head)

print_singly_linked_list(llist1, ' ', fptr)
fptr.write('\n')

fptr.close()

``````
Copy The Code &
Advertisements