剑指Offer4

从尾到头打印链表

https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

题目

图片说明

思路

Code

使用栈:

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int> a;
        vector<int> res;

        while(head)     
        {
            a.push(head->val);    //将元素入栈  
            head = head->next;
        }
        while(!a.empty())    //当栈中元素不为空时
        {            
            res.push_back(a.top());    //读取栈顶元素放入vector向量
            a.pop();        //弹出栈顶元素
        }
        return res;
    }
};

递归:

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        //使用递归实现
        vector<int> res;
        if(!head)            //退出条件
            return res;
        res = printListFromTailToHead(head->next);    //这里必须有res返回值
        res.push_back(head->val);
        return res;
    }
};

reverse()函数:

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        while(head)
        {
            res.push_back(head->val);
            head = head->next;
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
全部评论

相关推荐

程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务