C++ Linux

Question : Remove Nth Node from end of list
Given a linked list, remove the n-th node from the end of list andreturn its head. Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked listbecomes 1->2->3->5.
Note:
Given n will always be valid. (i.e. n is greater than 0)
Follow up:
Could you do this in one pass?
Hint: Maintain two pointers and update one with a delay of nsteps.

list.h

#ifndef LIST_H
#define LIST_H

struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next){}

};

#endif

list.cpp

#include

#include "list.h"

using namespace std;

ListNode* removeNthFromEnd(ListNode* head, int n);

string print_list_to_str(ListNode* head){
string temp = "";
ListNode* current = head;
while (current!=NULL){
temp +=to_string(current->val);
temp += "->";
current = current->next;
}
temp += "NULL" ;
return temp;
}

void print_list(ListNode* head){
ListNode* current = head;
while (current!=NULL){
cout << current->val<< "->";
current = current->next;
}
cout << "NULL" << endl;
}

ListNode* add_node(ListNode* head, int val){
ListNode* new_node = new ListNode(val);
ListNode* current = head;
if (current == NULL){
head = new_node;
return head;
}
while (current->next != NULL){
current = current ->next;
}
current->next = new_node;

return head;

}

void delete_list(ListNode** head){
ListNode* current = *head;
ListNode* temp = NULL;
while (current != NULL){
temp = current->next;
delete current;
current = temp;
}
*head = NULL;
}

void print_result (string actual, string expected, int num){
if (actual == expected)
cout << "Test " << num<< " pass" << endl;
else{
cout << "Test " << num<< " failed." << endl;
cout << "Your answer: "<< actual << endl;
cout << "Expected : "<< expected << endl;
exit(1);
}
}

void test1(string expected){
ListNode* l = NULL;
for (int i = 0; i < 4; i++)
l = add_node(l, i+1);

l = removeNthFromEnd(l, 4);
string actual = print_list_to_str(l);
delete_list(&l);

print_result(actual, expected, 1);
}

void test2(string expected){
ListNode* l = NULL;
for (int i = 0; i < 4; i++)
l = add_node(l, i+1);

l = removeNthFromEnd(l, 1);
string actual = print_list_to_str(l);
delete_list(&l);

print_result(actual, expected, 2);

}

void test3(string expected){
ListNode* l = NULL;
l = add_node(l, 5);

l = removeNthFromEnd(l, 1);
string actual = print_list_to_str(l);
delete_list(&l);

print_result(actual, expected, 3);

}

void test4(string expected){
ListNode* l = NULL;
l = add_node(l, 25);
l = add_node(l, 28);

l = removeNthFromEnd(l, 1);
string actual = print_list_to_str(l);
delete_list(&l);

print_result(actual, expected, 4);

}

void test5(string expected){
ListNode* l = NULL;
l = add_node(l, 15);
l = add_node(l, 81);

l = removeNthFromEnd(l, 2);
string actual = print_list_to_str(l);
delete_list(&l);
print_result(actual, expected, 5);

}

void test6(string expected){
ListNode* l = NULL;
for (int i = 0; i < 50000; i++)
l = add_node(l, i+1);

l = removeNthFromEnd(l, 25000);
string actual = print_list_to_str(l);
delete_list(&l);
print_result(actual, expected, 6);

}

memory.cpp

#include

#include

int get_memory_usage_kb(long* vmrss_kb, long* vmsize_kb)
{
/* Get the the current process' status file from the procfilesystem */
FILE* procfile = fopen("/proc/self/status", "r");

long to_read = 8192;
char buffer[to_read];
int read = fread(buffer, sizeof(char), to_read, procfile);
fclose(procfile);

short found_vmrss = 0;
short found_vmsize = 0;
char* search_result;

/* Look through proc status contents line by line */
char delims[] = "";
char* line = strtok(buffer, delims);

while (line != NULL && (found_vmrss == 0 || found_vmsize== 0) )
{
search_result = strstr(line, "VmRSS:");
if (search_result != NULL)
{
sscanf(line, "%*s %ld", vmrss_kb);
found_vmrss = 1;
}

search_result = strstr(line, "VmSize:");
if (search_result != NULL)
{
sscanf(line, "%*s %ld", vmsize_kb);
found_vmsize = 1;
}

line = strtok(NULL, delims);
}

return (found_vmrss == 1 && found_vmsize == 1) ? 0 :1;
}

task2_main.cpp

#include
#include
#include
#include
#include "list.h"
using namespace std;

string print_list_to_str(ListNode* head);
void print_list(ListNode* head);
ListNode* add_node(ListNode* head, int val);
void delete_list(ListNode** head);
void print_result (string actual, string expected, int num);
void test1(string expected);
void test2(string expected);
void test3(string expected);
void test4(string expected);
void test5(string expected);
void test6(string expected);
int get_memory_usage_kb(long* vmrss_kb, long* vmsize_kb);

int main(int argc, char const *argv[])
{
//variables for memory calculation
long vmrss, vmsize;

//construct expected results
ListNode* t1 = NULL;
for (int i = 1; i < 4; i++)
t1 = add_node(t1, i+1);
string expected1 = print_list_to_str(t1);

ListNode* t2 = NULL;
for (int i = 0; i < 3; i++)
t2 = add_node(t2, i+1);
string expected2 = print_list_to_str(t2);

ListNode* t3 = NULL;
string expected3 = print_list_to_str(t3);

ListNode* t4 = NULL;
t4 = add_node(t4, 25);
string expected4 = print_list_to_str(t4);

ListNode* t5 = NULL;
t5 = add_node(t5, 81);
string expected5 = print_list_to_str(t5);

ListNode* t6 = NULL;
for (int i = 0; i < 25000; i++)
t6 = add_node(t6, i+1);
for (int i = 25001; i < 50000; i++)
t6 = add_node(t6, i+1);
string expected6 = print_list_to_str(t6);

//get time stamp before testing
auto start = chrono::high_resolution_clock::now();

//testing
test1(expected1);
test2(expected2);
test3(expected3);
test4(expected4);
test5(expected5);
test6(expected6);

//get time stamp after testing
auto end = chrono::high_resolution_clock::now();

//calculate and print time taken
double time_taken =
chrono::duration_cast(end -start).count();
time_taken *= 1e-9;

cout << "Time taken by program is : " << fixed
<< time_taken << setprecision(9);
cout << " sec" << endl;

get_memory_usage_kb(&vmrss, &vmsize);
printf("Current memory usage: VmRSS = %6ld KB, VmSize = %6ld KB",vmrss, vmsize);

return 0;
}

solution2.cpp

#include

#include "list.h"
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/

ListNode* removeNthFromEnd(ListNode* head, int n) {
//Type your answer here:
}

Answer rating: 100% (QA)

ListNode removeNthFromEndListNode head int n ListNode temp head int count 0 while tem... View the full answer