数据结构——求单向链表的倒数第K个节点

首先，对于链表来说，我们不能像数组一样直接访问，所以我们想到要求倒数第K个节点首先要知道最后一个节点。

然后从最后一个节点往前数K个。

最后得到想要的值。

但是这是不对的，为什么呢？因为题目给出的是单向链表，只能从前往后找。

所以我们需要换一种思路。

定两个指针。

都从链表的头开始走，一个先走一个后走，先走的比后走的快k步。

然后两个人之后每次都走一步。

当先走的走到终点的时候。

那么后走的所在的位置就是倒数第K个节点的位置了。

下面是代码，这次使用STL库中的list完成。

/**

*单向链表求倒数的第K个节点的值

**/

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <list>

using namespace std;

//定义一个链表

list<int> linklist;

//打印链表中的元素

void print_list()

{

    list<int>::iterator linklistIterator;

    for(linklistIterator=linklist.begin(); linklistIterator!=linklist.end(); linklistIterator++)

        cout<<*linklistIterator<<" ";

    cout<<endl;

}

int main()

{

    //创建链表中的元素

    for(int i=; i<=; i++)

        linklist.push_back(i);

    print_list();

    //要求寻找到，倒数第3个元素。

    int k=;

    list<int>::iterator iterator_A=linklist.begin();

    list<int>::iterator iterator_B=linklist.begin();

    for(int i=; i<=k; i++)

        iterator_A++;

    while(iterator_A != linklist.end())

    {

        iterator_A++;

        iterator_B++;

    }

    cout<<"倒数第三个元素是："<<*iterator_B<<endl;

    return ;

}