将第 k 个元素打印到链表中的最后一个元素的算法

Question

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

“实现一种算法来查找单向链表的第 k 个到最后一个元素。”

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

#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

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

解决面试问题是一种很好的学习方式，但您应该尝试花时间了解为什么它自己不起作用。作为一名程序员，您将大部分时间花在阅读和调试代码上，而这项技能是通过将大量时间准确地投入到像a debugger.

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

其次，您需要line by line使用调试器运行代码并relevant variables在每行之后检查所有代码以查看它们是否具有预期值。要知道它们是什么relevant variables需要时间和经验，但如果你练习，你就会到达那里。

第三步也是最后一步是重复第二步，直到您really understand发现问题所在。我不是在谈论trial and error until it works，我是在谈论了解why变量没有预期值。搜索 SO，阅读标准，提出非常具体的问题等等，但不要让其他人为您进行调试，因为他们会获得此技能而您不会