剑指offer之反向打印链表值

1 问题

反向打印链表值

 
2 思考

1） 我们利用栈的思想，新进后出，把链表的每个元素分别入栈之后再打印栈

2）既然上面用到了栈，我们应该就会想到用到递归来实现

 
3 代码实现

    #include <iostream>
    #include <stack>
    #include <stdlib.h>
     
    using namespace std;
     
    typedef struct node
    {
        int value;
        struct node *next;
    } Node;
     
    /**
     *把链表的每一个元素遍历出来放进栈,然后利用
     *栈把先进后出的特点,然后打印栈
     */
    void reverse_printf(Node *head)
    {
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return;   
        }
        Node *p = head;
        stack<Node *> stk;   
        while (p != NULL)
        {
            stk.push(p);
            p = p->next;
        }
        while(!stk.empty())
        {
            Node *node = stk.top();
            std::cout << node->value << std::endl;
            stk.pop();
        }
    }
     
    /**
     *既然上面用到了栈,那么我们自然而然就会想到
     *用递归的思想,我们就自己调用自己直到遍历到最后
     *很明显我们递归的条件是最后一个原始的next不能为空
     */
    void reverse_printf1(Node *head)
    {
        /**这样也行
        if (head == NULL)
        {
            return;   
        }
        reverse_printf1(head->next);
        std::cout << head->value << std::endl;**/
        if (head != NULL)
        {
            reverse_printf1(head->next);
            std::cout << head->value << std::endl;
        }
    }
     
     
    void printf(Node *head)
    {
        if (head == NULL)
        {
            std::cout << "head is NULL" << std::endl;
            return;   
        }
        Node *p = head;
        while (p != NULL)
        {
            std::cout << p->value << std::endl;
            p = p->next;
        }
    }
     
    int main()
    {
        Node *head = NULL;
        Node *node1 = NULL;
        Node *node2 = NULL;
        Node *node3 = NULL;
        head = (struct node*)malloc(sizeof(Node));
        node1 = (struct node*)malloc(sizeof(Node));
        node2 = (struct node*)malloc(sizeof(Node));
        node3 = (struct node*)malloc(sizeof(Node));   
        if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL)
        {
            std::cout << "malloc fail" << std::endl;
            return -1;
        }
        head->value = 0;
        head->next = node1;
     
        node1->value = 1;
        node1->next = node2;
     
        node2->value = 2;
        node2->next = node3;
     
        node3->value = 3;
        node3->next = NULL;
           
        printf(head);
        std::cout << "***************" << std::endl;
        reverse_printf(head);
        std::cout << "***************" << std::endl;
        reverse_printf1(head);
        free(head);
        free(node1);
        free(node2);
        free(node3);
        return 0;
       
    }
    
 
 
4 运行结果

    0
    1
    2
    3
    ***************
    3
    2
    1
    0
    ***************
    3
    2
    1
    0

 



 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)