Delete a specified node from a singly linked list. The head pointer is not provided.
/*
* DeleteSpecificNode.cpp
*
* Created on: Apr 18, 2012
* Author: Kiran Hegde
*/
#include <iostream>
#include <cstdlib>
#include <time.h>
using namespace std;
struct Node {
int data;
Node *next;
};
/**
* Generate a linked list of length "size" containing random numbers from 0 to 9
*/
Node *createLinkedList(int size) {
srand(time(NULL));
Node *head = NULL;
for (int i = 0; i < size; i++) {
Node *node = new Node;
node->data = rand() % 10;
node->next = head;
head = node;
}
return head;
}
void deleteLinkedList(Node *head) {
while (head != NULL) {
Node *temp = head;
head = head->next;
delete temp;
}
}
void printLinkedList(Node *head) {
Node *curr = head;
while (curr != NULL) {
cout << curr->data << "-->";
curr = curr->next;
}
cout << "EMPTY" << endl;
}
Node *getNthNodeFromStart(Node *head, int index) {
int count = 0;
Node *curr = head;
while (count < index-1) {
curr = curr->next;
count ++;
}
return curr;
}
/**
* The following operations will effectively delete the current node:
* - Make the specific node's data the same as the next node's.
* - Make the pointer to next equal to pointer to next to next
* - Delete the next node
*/
bool deleteSpecificNode(Node * &specNode) {
if ((specNode == NULL) || (specNode->next == NULL)) {
return false;
}
Node *temp = specNode->next;
specNode->data = specNode->next->data;
specNode->next = specNode->next->next;
delete temp;
return true;
}
/**
* Test the function
*/
int main() {
Node *head = createLinkedList(15);
cout << "Original List: " << endl;
printLinkedList(head);
Node *node = getNthNodeFromStart(head, 5); //5th node from start
deleteSpecificNode(node);
cout << "After Deleting 5th node from start: " << endl;
printLinkedList(head);
deleteLinkedList(head);
return 0;
}