2.2 Implement an algorithm to find the kth to last element of a singly linked list.

2.2.cpp

#include<iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
    
    Node(int data, Node *next) {
        this->data = data;
        this->next = next;
    }
    
    ~Node() {}
};

typedef Node* pNode;

pNode last1(pNode head, int k)
{
    pNode *a = new pNode[k];
    int end = 0;
    while (head != nullptr) {
        a[end++] = head;
        end %= k;
        head = head->next;
    }
    pNode r = a[end];
    delete a;
    return r;
}

pNode last2(pNode head, int k, int &i)
{
    if (head == nullptr) return nullptr;
    pNode p = last2(head->next, k, i);
    if (++i == k) {
        return head;
    }
    return p;
}

pNode last3(pNode head, int k)
{
    pNode p = head;
    
    for (int i = 0; i < k-1; i++) {
        head = head->next;
    }
    
    while (head->next != nullptr) {
        head = head->next;
        p = p->next;
    }
    
    return p;
}

void print(Node * head)
{
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

void clear(Node *head)
{
    if (head != nullptr) {
        while(head->next != nullptr) {
            Node *t = head->next;
            head->next = t->next;
            delete t;
        }
        delete head;
    }
}

int main(int argc, char *argv[])
{
    Node *list = new Node(0, new Node(1, new Node (2, new Node(3, new Node(4, nullptr)))));
    print(list);
    cout << last1(list, 5)->data << endl;
    int i = 0;
    cout << last2(list, 4, i)->data << endl;
    cout << last3(list, 3)->data << endl;
    clear(list);
    return 0;
}