C++开发常见算法和数据结构面试题（持续更新）

1.给定一个单向链表（长度未知），请设计一个既节省时间又节省空间的算法来找出该链表中的倒数第m个元素。实现这个算法，并为可能出现的特例情况安排好处理措施。“倒数第m个元素”是这样规定的：当m=0时，链表的最后一个元素将被返回。

解决问题方法思路如下：

方法（双指针法）：头结点指针为当前指针，尾节点指针为拖后指针。开始的时候当前指针和拖后指针初始化为链表的头结点，首先我们让当前指针遍历到第m个元素，拖后指针不变；然后同步更新当前指针和拖后指针；直到当前指针为链表结尾。这样我们就能保证当前指针和拖尾指针之间的距离是m。

代码如下：

Node* FindMToLastNode(Node* pHead, int m)  {  // 查找到第m个元素  Node* pCurrent = pHead;  for (int i = 0; i < m; ++i)  {  if (pCurrent)  {  pCurrent = pCurrent->next;  }  else  {  return NULL;  }  }  Node* pFind = pHead;  while (pCurrent)  {  pFind = pFind->next;  pCurrent = pCurrent->next

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！