剑指offer刷题笔记六：从尾到头打印链表（正式题解）

飞熊 • 2023年4月6日下午12:54 • 后端笔记 • 阅读 177

注：链表的实现见上一篇文章链接: 剑指offer刷题笔记六：从尾到头打印链表（前导文章之一文搞懂C++单向链表）.

题目：输入一个链表的头节点，反过来打印出每个结点的值。
分析：一共采取三种方法。
1、将链表中的结点指针反转过来，即改变链表的方向。此种方法比较容易想到，但是会遇到改变原来链表结构的问题。
2、用栈实现先进后出的顺序，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出每个结点的值，此时输出的结点的顺序已经反转过来。
3、利用递归来实现，递归本质上也是一个栈结构。
代码：
链表的实现见文章开头链接所指向的文章。以下展示反向输出的代码。

#include <iostream>
#include"ListNode.h"
#include<stack>//利用栈是需要包含的头文件

void method1(ListNode* pNode1, ListNode* pNode2, ListNode* pNode3) {//方法一：改变链表结构
    ConnectListNodes(pNode3, pNode2);
    ConnectListNodes(pNode2, pNode1);

    pNode1->m_pNext = nullptr;

    PrintList(pNode3);
}

void method2(ListNode* pHead) {//方法二：利用栈结构
    std::stack<ListNode*>nodes;
    ListNode* pNode = pHead;
    while (pNode != nullptr) {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }

    while (!nodes.empty()) {
        pNode = nodes.top();
        std::cout << pNode->m_nValue << "\t";
        nodes.pop();
    }
    std::cout << std::endl;
}

void method3(ListNode* pHead) {//利用递归
    if (pHead != nullptr) {
        if (pHead->m_pNext != nullptr) {
            method3(pHead->m_pNext);
        }
        std::cout << pHead->m_nValue << "\t";
    }
}
int main()
{
    std::cout << "Test begins!\n";
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);

    //PrintList(pNode1);//从前往后打印链表
    //method1(pNode1, pNode2, pNode3);//使用方法1
    //method2(pNode1);//使用方法2
    method3(pNode1);//使用方法3

    DestroyList(pNode1);
    
    std::cout << "\nTest ends!\n";
}