CareerCup2.2.cpp

CareerCup2.2.cpp

/**
 * Chapter 2
 *
 * 2.2 Implement an algorithm to find the kth to last element of a singly linked list.
 */
#include <iostream>

using namespace std;

// Define a Node class
class Node {
public:
    int data;
    Node* next;
    
    Node(int num) {
        data = num;
        next = NULL;
    }
};

// Generate a linked-list, return a head pointer
Node* init(int a[], int n) {
    if (n == 0)
        return NULL;
    Node* s = new Node(a[0]);
    //    cout << s->data << endl;
    Node* p = s;
    for (int i = 1; i < n; ++i) {
        Node* t = new Node(a[i]);
        p->next = t;
        p = p->next;
    }
    return s;
}

// Print the linked list
void print(Node* head){
    Node* p = head;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
}


// Find kth to the last element
// k starts from 1
Node* findKth(Node* head, int k) {
    // Error Check
    if (head == NULL)
        return NULL;
    if (k < 1) {
        cout << "k should start from 1" << endl;
        return NULL;
    }
    // Iterate once to get the kth node location
    Node* p = head;
    int count = 0;
    while(p) {
        ++count;
        if (count < k && p->next == NULL)
            cout << "k is larger than total number of nodes." << endl;
        else if (count == k )
            return p;
        
        p = p->next;
    }
    return NULL;
}

// Main Function to test
int main(int argc, char const *argv[])
{
    int a[] = {1, 2, 3, 4, 5, 6};
    int size = sizeof(a) / sizeof(int);
    Node* head = init(a, size);
    Node* kth = NULL;
    
    print(head);
    print(findKth(head, 0));
    print(findKth(head, 100));
    cout << endl;
    kth = findKth(head, 3);
    print(kth);
    return 0;
}