Find the Nth node from the last in a linked list.
/*
* NthToLastNode.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 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 *findNthToLastNode(Node *head, int N) {
Node *p1 = head;
Node *p2 = head;
if (p2 == NULL)
return NULL;
//Move p2 N nodes into the list
int count=0;
while (count < N) {
p2 = p2->next;
count ++;
if (p2 == NULL)
return NULL;
}
//Now move both nodes till p2 reaches the end of list
while (p2 != NULL) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
/**
* Test the code
*/
int main() {
Node *head = createLinkedList(15);
cout << "Original List: ";
printLinkedList(head);
int randNum = (rand() % 10) + 1; // random number between 1 and 10
Node *nthToLast = findNthToLastNode(head, randNum);
cout << randNum << "th node from the last: = " << nthToLast->data << endl;
deleteLinkedList(head);
return 0;
}