Return Kth to Last

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

// simulating recursive operation
int kthtolast(Node *head, int k) {
    stack<Node*> s;
    Node *iter = head;
    s.push(iter);

    while (iter) {
        s.push(iter->next);
        iter = iter->next;
    }

    s.pop(); // remove null
    int count = 0;
    while (count < k) {
        count++;
        s.pop();
        if (s.empty()) {
            return INT_MIN;
        }
    }

    return s.top()->value;
}


int main()
{
    LinkedList LL1;
    srand(time(nullptr));
    int counter = 0;
    int random;

    while (counter <= 100) {
        random = rand() % 1000 + 2;
        LL1.insert(random);
        counter++;
    }

    LL1.print();
    cout << LL1.kthtolast(LL1.front, 1) << endl;
    cout << LL1.kthtolast(LL1.front, 0) << endl;
    cout << LL1.kthtolast(LL1.front, 10) << endl;
    cout << LL1.kthtolast(LL1.front, 1000) << endl;
    pause();
}

// recursively

Node * kthtolast2(Node *head, int k,int &count) {
    if (!head) return nullptr;

    Node *temp = kthtolast2(head->next, k, count);

    ++count;
    if (count - 1 == k) {
        return head;
    }
    return temp;
}


int kthtolast(Node *head, int k) {
    int count = 0;
    Node *ret = kthtolast2(head, k, count);
    if (!ret) return INT_MIN;
    return ret->value;
    pause();
}

2.2b Remove jth to Last: Implement an algorithm that removes the jth to last element in a linked list.

• The approach I took with this can also be used for 2.2a. The idea is that if you increment one point j amount of times, and have a second point start from the first while iterating both to the end, when the first pointer stops will be when the second pointer is at j.

Node* removejthtolast(Node *front, int j) {
    // increment pointer 1 to j
    Node *itr = front;
    if (!itr || j < 0) return nullptr;
    for (int i = 0; i < j; i++) {
        itr = itr->next;
        if (!itr) return nullptr;
    }
    Node* itr2 = front;
    Node* prev = nullptr;
    while (itr->next) {
        prev = itr2;
        itr2 = itr2->next;
        itr = itr->next;
    }

    prev->next = itr2->next;
    delete itr2;
}