【剑指Offer | C++ 】面试题6：替换空格

输入一个链表的头节点，从尾到头反过来打印出每个节点的值，不允许修改输入数据（不能改变链表的节构）。链表节点定义如下：

struct ListNode()
{
	int m_nKey;
	ListNode* m_pNext;
}
1
2
3
4
5

• 解法①：逆向用栈
  遇到逆向题第一反应：万能栈Stack

#include
#include
using namespace std;

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

int main() {
    /* 构建链表 */
    ListNode* node1 = new ListNode();
    ListNode* node2 = new ListNode();
    node1->m_nKey = 1;
    node2->m_nKey = 2;

    node1->m_pNext = node2;
    node2->m_pNext = nullptr;

    ListNode* head = node1;

    /* 开始算法 */
    stack<ListNode*> nodes;
    while (head != nullptr) {
        nodes.push(head);
        head = head->m_pNext;
    }

    while (!nodes.empty()) {
        head = nodes.top();
        cout << head->m_nKey << "\n";
        nodes.pop();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• 解法②：栈 可使用递归实现
  需要注意链表太长不可使用此种方法

#include
using namespace std;

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

void recursion(ListNode* node) {
    if (node != nullptr) {
        recursion(node->m_pNext);
        cout << node->m_nKey;
    }
    
}

int main() {
    /* 构建链表 */
    ListNode* node1 = new ListNode();
    ListNode* node2 = new ListNode();
    node1->m_nKey = 1;
    node2->m_nKey = 2;

    node1->m_pNext = node2;
    node2->m_pNext = nullptr;

    ListNode* head = node1;

    /* 开始算法 */
    recursion(head);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

报错：

“->”: 非函数声明符后不允许尾随返回类型

对链表的操作不能直接放在函数外……