将第 k 个元素打印到链表中的最后一个元素的算法 [英] Algorithm to print kth to last element in a linked list

问题描述

我正在阅读 Cracking the Coding Interview 并做练习题，但我一直坚持这个问题:

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

"实现一个算法来找到单个元素的第k个到最后一个元素链表."

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

我的递归函数没有返回任何东西，我不知道为什么.在递归函数中，我采用了 3 个参数.K 将是我们想要找出的最后一个元素的位置.Node* temp 将是头节点， int i 将保留最后一个节点的元素计数.

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;

    }
};

推荐答案

不是这个问题的答案，但我认为这比实际的解决方案更重要.

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.

首先，您需要调试器，根据您的操作系统，您可以选择 Windows 上的 Visual Studio 社区版、Mac 上的 xcode 或 Linux 上的 gdb/lldb.我建议您从 MSVC 或 xcode 开始，因为它们对初学者友好，稍后再学习如何使用 Linux 工具 - 它们是有经验的程序员必备的技能.

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.

第三步也是最后一步是重复第二步，直到您真正理解问题出在哪里.我不是在谈论试错直到它起作用，我在谈论理解为什么变量没有预期值.搜索 SO，阅读标准，提出非常具体的问题等等，但不要让其他人为您进行调试，因为他们会获得此技能而您不会

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

这篇关于将第 k 个元素打印到链表中的最后一个元素的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！