Comment on page

# 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;
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()
{
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) {
Node *temp = kthtolast2(head->next, k, count);
++count;
if (count - 1 == k) {
}
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;
}