从尾到头打印链表

作者: gaookey | 来源:发表于2021-10-28 17:08 被阅读0次

单向链表的节点定义

// 单向链表的节点定义
struct ListNode {
    int m_nValue;
    ListNode* m_pNext;
};

栈实现

// 栈实现
void PrintListReversingly_Iteratively(ListNode* pHead) {
    // #include <stack>
    std::stack<ListNode*>nodes;
    
    ListNode* pNode = pHead;
    while (pNode != nullptr) {
        nodes.push(pNode);
        pNode = pNode->m_pNext;
    }
    
    while (!nodes.empty()) {
        pNode = nodes.top();
        printf("%d\t", pNode->m_nValue);
        nodes.pop();
    }
}

递归实现

当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。

// 递归实现
void PrintListReversingly_Recursively(ListNode* pHead) {
    if (pHead != nullptr) {
        if (pHead->m_pNext != nullptr) {
            PrintListReversingly_Recursively(pHead->m_pNext);
        }
        printf("%d\t", pHead->m_nValue);
    }
}