Question

C++ Linux

Question : Remove Nth Node from end of list
Given a linked list, remove the n-th node from the end of list and return its head. Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 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 n steps.

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

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

#include <memory.h>

int get_memory_usage_kb(long* vmrss_kb, long* vmsize_kb)
{
/* Get the the current process' status file from the proc filesystem */
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[] = "\n";
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 <iostream>
#include <chrono>
#include <iomanip>
#include <unistd.h>
#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<chrono::nanoseconds>(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\n", vmrss, vmsize);

  
   return 0;
}

solution2.cpp

#include <iostream>

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

Approach:

Take two pointers , first will point to the head of the linked list and second will point to the Nth node from the beginning. Now increment both pointers by one at the same time until second pointer points to the last node of the linked list. When the second pointer is pointing to the last node, the first pointer will be pointing the Nth node from end which is to be deleted.

Here is the code:

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

// First pointer will point to the head of the linked list

        ListNode *first = head;

  

        // Second pointer will poin to the Nth node from the beginning

        ListNode *second = head;

        for (int i = 0; i < n; i++)

        {

  

            // If count of nodes in the given linked list is <= n

            if (second->next == NULL)

            {

  

                // If count = n i.e delete the head node (if n = length of Linked list)

                if (i == n - 1)

                    head = head->next;

                return head;

            }

            second = second->next; // taking second pointer to Nth node

        }

  

        // Increment both the pointers by one until second pointer reaches the end

        while (second->next != NULL)

        {

            first = first->next;

            second = second->next;

        }

  

        // First must be pointing to the

        // Nth node from the end by this time

        // So, delete the node the first pointer is pointing to

        first->next = first->next->next;

        return head;

}

As i have written a function only i will not be able to attach outputs, please ask if any doubts in the comments section. Thanks!