Algorithm to print kth to last element in a linked list

Question

I'm reading Cracking the Coding Interview and doing practice problems and I'm stuck on this one:

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

My recursive function is not returning anything and I am not able to figure out why. In the recursive function I am taking 3 parameters. K will be the position from the last element that we want to find out. Node* temp will be the head node and int i will keep a count of elements from the last node.

#include<bits/stdc++.h>
using namespace std;

class Node
{
    int data;
    Node* next;
    public:
    Node(){
        data=0;
        next=NULL;
    }

    friend class LinkedList;
};

class LinkedList
{
    public:
    Node* head;
    public:
    LinkedList(){
        head=NULL;
    }

    void append(int data){
        Node* temp= new Node();
        temp->data=data;
        temp->next=NULL;
    
        if (head==NULL){
            head=temp;
            
        }
        else{
        Node* ptr=head;
        while(ptr->next!=NULL){
            ptr=ptr->next;
        }
        ptr->next=temp;
        }

    }

    void display(){
        Node* ptr=head;
        if(head==NULL){
            cout<<"List is empty"<<endl;
            return;
        }
        while(ptr!=NULL){
            cout<<ptr->data<<"->";
            ptr=ptr->next;

        }
        cout<<"NULL";
    }
   //using recursive solution
    int kth_to_last2(int k,Node* temp,int &i){
        if(temp==NULL){
            return 0;
        }
        int index=kth_to_last2(k,temp->next,i);
        i++;
        if(i==k){
            return temp->data;
        }
        cout<<endl;
        return index;

    }
};

Answer 1

Not an answer to this question, but I think this is more important than the actual solution.

Solving interview questions is a great way to learn, but you should try to spend the time to understand why it doesn't work by yourself. As a programmer you'll spend most of your time reading and debugging code and this skill is acquired by investing a huge amount of time exactly on cases like this one with a debugger.

First you need a debugger and depending on your OS you can pick Visual Studio Community edition on Windows, xcode on Mac or gdb/lldb on Linux. I would recommend you to start with MSVC or xcode as they are beginner friendly and learn how to use Linux tools later - they are a must have skill for experienced programmers.

Second you need to run your code line by line using the debugger and inspecting all relevant variables after each line to see if they have the expected value or not. To know which are they relevant variables takes time and experience, but you'll get there if you practice.

Third and final step is to repeat second step until you really understand what was the problem. I'm not talking about trial and error until it works, I'm talking about understand why the variables don't have the expected value. Search SO, read the standard, ask very specific questions and so on, but don't let others do the debugging for you as they will acquire this skill whilst you won't

Answer 2

As most list questions, you might need several "iterators" to solve it:

class LinkedList
{
private
    // ...

    std::optional<Node*> next(Node* n, std::size_t k)
    {
        for (std::size_t i = 0; i != k; ++i) {
            if (n == nullptr) { return std::nullopt; }
            node = node->next;
        }
        return node;
    }
public:
    // ...

    std::optional<Node*> kth_to_last(std::size_t k)
    {
        auto endNode = next(head, k);
        if (!endNode) { return nullopt; } // list size < k
    
        auto res = head;
        while (*endNode != nullptr) {
            *endNode = (*endNode)->next;
            res = res->next;
        }
        return res;
    }
};

Note: If you cannot use std::optional, std::pair<bool, Node*> is a possible replacement.

Answer 3

While the other answers are (mostly) correct they don't address the specific problem here.

    int kth_to_last2(int k,Node* temp,int &i){
        if(temp==NULL){
            return 0; // Is zero a value that does not appear in data? (1)
        }
        int index=kth_to_last2(k,temp->next,i); // recursion, how deep will it go? (2)
        i++;
        if(i==k){ // do we have a off-by-one error? (3)
            return temp->data;
        }
        cout<<endl; // why is this here, left by an earlier debug attempt?
        return index;
    }

1. You must be able to differentiate between valid data and errors, if zero is guaranteed to not appear in data this is OK, else a possible solution is std::optional/std::pair like @Jarod42 suggested.
2. Recursion is problematic because we risk a stack overflow (from which this very site is named) prefer iterative if at all possible. Recursions are easier, less messy than iterations but are the path to the dark side ie. stack overflow.
3. Make some very simple tests to check that you don't have an off-by-one error.
4. std::endl is very good for programs that crash and you want to be sure the data is written before the crash, else its mostly only making your programs slow.

Now as a much simpler solution I would advice either counting the nodes and then advance to the n-kth node.

untested code

int n = 0;
while(node != nullptr) {
  node = node->next;
  n++;
}

Then use the a next or advance function to move to the kth last node.

Or add a size data member to the list and keep it up to date then you only need the second part with the advance function.