例4，设计一个算法求出单链表的倒数第m个结点，要求不得求出链表长度，不得对链表进行逆转，如果找到该结点就返回它的地址，否则就返回NULL。

     【分析】该题目要求求出单链表的倒数第m个结点，但又不能逆转单链表。

      我们知道，获取单链表顺数第i个结点的方式是：设置指针p=head，从头指针开始循环执行p=p->next，一步一步往后移，直到第i个结点为止。

      这里我们变动一下，再增加一个指针q，使指针q也沿着链表移动，并且比指针p落后m-1步，当p到达链表尾部时，q刚好指向倒数第m个结点。

具体实现如下：

//实现文件，find_M.cpp

#include <iostream>
#include "LinkList.h"
using namespace std;

ListNode<int>* searchNodeM(LinkList<int> *link,int m)
{
	ListNode<int> *p = link->getNode(1); //p初始化为链表的第一个结点
	if (p != NULL && m > 0)
	{
		for (int i=1;i<m;i++)
		{
			p = p->getNext();
			if (p == NULL)
			{
				cout<<"该链表没有倒数第m个结点"<<endl;
				return NULL;
			}
		}
	}

	ListNode<int> *q = link->getNode(1); //设置指针q,让它位于p之后
	while(p->getNext() != NULL) //同时移动两个指针，直到p到达表尾
	{
		p=p->getNext();
		q=q->getNext();
	}
	return q;

}

void main()
{
	LinkList<int> *head = new LinkList<int>();
	int m,i;
	for (i=1;i<=10;i++)
	{
		head->insertNode(i*3); //数列为3,6,9,12,15,18,21,24,27,30
	}
	cout<<"输入m的值为: "<<endl;
	cin>>m;
	ListNode<int> *p = searchNodeM(head,m);
	for (i=1;i<=10;i++)
	{
		cout<<head->getNodeData(i)<<" ";
	}
	cout<<endl;
	cout<<"倒数第"<<m<<"个结点: "<<p->getData()<<endl;

}

#include <iostream>

//链表结构
template<typename DataType> class ListNode;
template<typename DataType> class LinkList
{
	public:
		LinkList()
		{
			head = new ListNode<DataType>();
		}

		LinkList(ListNode<DataType> *firstNode)
		{
			head = firstNode;
		}

		//析构函数
		~LinkList(){
			delete head;
		}

		//在第i个节点后插入节点
		bool insertNode(int index,DataType newData);
		//在表尾插入新节点
		bool insertNode(DataType newData);
		//删除节点
		bool removeNode(ListNode<DataType> *q);
		//查找指定值的节点，并返回地址
		ListNode<DataType>* findNode(DataType value);
		//清空链表
		void cleanLink();
		//获取第i个结点中的数据
		DataType getNodeData(const int index);
		//获取链表长度
		int getLength();
		//查找链表的第i个元素
		ListNode<DataType>* getNode(int i);
	private:
		ListNode<DataType> *head; //头结点

};

//定义链表结点
template <typename DataType> class ListNode
{
	public:
		ListNode(){
			next = NULL;
		}
		ListNode(const DataType item,ListNode<DataType> *nodeNext = NULL)
		{
			data = http://www.mamicode.com/item;>
效果如下：
图（1）在数组{3，6，9，12，15，18，21，24，27，30}中查找倒数第3个元素，得到的元素为24

参考文献： 胡浩.妙趣横生的算法(C++语言实现).北京.清华大学出版社.2014

查找单链表中的倒数第m个结点