# 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;
}``````

Last updated