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

     【分析】该题目要求求出单链表的倒数第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;  }

//头文件，LinkList.h

#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 = item;    next = nodeNext;   }   ~ListNode()   {    next = NULL;   }   //获取结点内的数据   DataType getData()   {    return data;   }   //获取指针域   ListNode* getNext()   {    return next;   }   private:   friend class LinkList<DataType>; //将LinkList设为友元类，                                    // 以方便访问node的数据成员和方法   ListNode<DataType> *next; //指向下一个结点的指针   DataType data;  //节点中的数据  };  //在链表的第i个结点后插入新结点 template<typename DataType> bool LinkList<DataType>::insertNode(int i,DataType newData) {  ListNode<DataType> *p = head;  //设置游标指针，初始化为头结点的地址  int j;  for (j=1;j<=i-1;j++)  //查找第i个结点，指针需要移动i-1次  {   p = p->next;   if (p == NULL) //如果该指针为空，表示不存在该结点，或者已到表尾   {    break;   }  }   if (p==NULL && j<(i-1)) //指针为空且没有到第i个位置,说明不存在第i个结点  {   std::cout<<"插入位置无效！"<<endl;   return false;  }  ListNode<DataType> *node = new ListNode<DataType>(newData); //创建新结点node  node->next = p->next;  //将node的next指针赋值为p的后继结点地址  p->next = node;    //p的后继指针指向node  return true;  }  //在单链表的表尾添加新结点 template<typename DataType> bool LinkList<DataType>::insertNode(DataType newData) {  ListNode<DataType> *p = head;                          //设置游标指针  ListNode<DataType> *node = new ListNode<DataType>(newData); //创建新结点  if (node==NULL)            //如果新结点内存分配失败，返回false  {   return false;  }   while(p->next != NULL) //遍历单链表，找到尾结点  {   p = p->next;  }  p->next = node;  return true;  }  //删除指定结点 template<typename DataType> bool LinkList<DataType>::removeNode(ListNode<DataType> *q) {  if (q == NULL)  {   std::cout<<"待删除结点不存在！"<<std::endl;   return false;  }  ListNode<DataType> *tempPointer = head; //设置游标指针，初始化为头结点  while(tempPointer->next != q) //遍历单链表，找到结点q的前驱结点  {   tempPointer = tempPointer->next;  }  tempPointer->next = q->next; //将结点q的后继结点地址值赋给其前驱结点的next的指针  delete q;  return true;  }  //查找指定结点值 template<typename DataType> ListNode<DataType>* LinkList<DataType>::findNode(DataType value) {  ListNode<DataType> *currentPointer = head; //设置游标指针  //判断游标指针所指结点的值是否与value相等  while(currentPointer != NULL && currentPointer->data != value)  {   currentPointer = currentPointer->next;  }  if (currentPointer == NULL)  {   std::cout<<"没有找到该结点,程序退出!"<<endl;   exit(1);  }  else{   return currentPointer  } }  //清空链表 template<typename DataType> void LinkList<DataType>::cleanLink() {  ListNode<DataType> *current = head; //设置游标指针  while(head->next != NULL)  {   current = head->next;   //将current指向head的后继结点   head->next = current->next; //将current的后继地址赋值给head的next域   delete current;      //回收current结点所占的空间  } }  //获取结点数据 template<typename DataType> DataType LinkList<DataType>::getNodeData(int index) {  int linkLength = getLength();  if (index < 1 || index > linkLength)  {   std::cout<<"结点不存在!"<<std::endl;   return false;  }    else  {   ListNode<DataType> *pmove = head->next;   for (int i=1; i<index && pmove; i++)   {    pmove = pmove->next;   }   return pmove->getData();  } }  //获取链表长度 template<typename DataType> int LinkList<DataType>::getLength() {  int count = 0;  ListNode<DataType> *p = head->next;  while(p!=NULL)  {   p = p->next;   count++;  }  return count; }  //查找链表的第i个元素 template<typename DataType> ListNode<DataType>* LinkList<DataType>::getNode(int i) {  ListNode<DataType> *p = head->next;   int j;  if (i<1 || i>getLength()-1) //带"头结点"，所以实际结点数需要减1  {   return false;  }  for (j=1;j<i;j++)  {   p = p->next;   if (p == NULL)   {    break;   }  }  if (p == NULL && j<i-1)  {   return false;  }   return p; }

效果如下：

图（1）在数组{3，6，9，12，15，18，21，24，27，30}中查找倒数第3个元素，得到的元素为24

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