C++开发常见算法和数据结构面试题（持续更新）_数据结构与算法面试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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24