Nth node from last in linked list

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