剑指Offer（三）：从尾到头打印链表

2017年11月22日10:25:17 14 27,336 °C

摘要

输入一个链表，返回一个反序的链表。

剑指Offer（三）：从尾到头打印链表

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入一个链表，返回一个反序的链表。

1、思路

通常，这种情况下，我们不希望修改原链表的结构。返回一个反序的链表，这就是经典的“后进先出”，我们可以使用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，给一个新的链表结构，这样链表就实现了反转。

2、代码

C++:

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int> nodes;
        vector<int> result;
        ListNode* node = head;
        while(node != NULL){
            nodes.push(node->val);
            node = node->next;
        }
        
        while(!nodes.empty()){
            result.push_back(nodes.top());
            nodes.pop();
        }
        return result;
    }
};

/**

* struct ListNode {

* int val;

* struct ListNode *next;

* ListNode(int x) :

* val(x), next(NULL) {

* }

* };

class Solution {

public:

vector<int> printListFromTailToHead(ListNode* head) {

stack<int> nodes;

vector<int> result;

ListNode* node = head;

while(node != NULL){

nodes.push(node->val);

node = node->next;

}

while(!nodes.empty()){

result.push_back(nodes.top());

nodes.pop();

}

return result;

}

};

Python2.7：

对于python来讲，不用如此麻烦，我们可以直接使用列表的插入方法，每次插入数据，只插入在首位。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        result = []
        while listNode:
            result.insert(0, listNode.val)
            listNode = listNode.next
        return result

# -*- coding:utf-8 -*-

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# 返回从尾部到头部的列表值序列，例如[1,2,3]

def printListFromTailToHead(self, listNode):

# write code here

result = []

while listNode:

result.insert(0, listNode.val)

listNode = listNode.next

return result

微信公众号

分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。

版权声明：本站原创文章，于2017年11月22日10:25:17，由 Jack Cui 发表，共 324 字。
转载请注明：剑指Offer（三）：从尾到头打印链表 | Jack Cui

发表评论取消回复

目前评论：14 其中：访客 8 博主 6

大敏广东省深圳市电信 3
回复 2018年9月8日上午9:26 沙发
请问一下大神，c++实现的时候为啥不直接result.push_back(node->val);，这可以少一个stack nodes;的使用
- Jack Cui Admin 辽宁省沈阳市东北大学三舍南(研究生)
  回复 2018年9月8日上午9:44 1层
  @大敏反转啊，先入先出。直接push_back需要再反转。
Irelia 湖南省湘潭市联通 1
回复 2019年2月21日下午2:14 板凳
不是很理解python中while lisNode 这句为什么能判断真假
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年2月21日下午6:43 1层
  @Irelia 空就是假了。
syq 广东省深圳市招商银行 1
回复 2019年2月28日下午7:22 地板
c++里面你申请的vector并没有用到啊
- Jack Cui Admin 北京市联通
  回复 2019年2月28日下午10:51 1层
  @syq 你再好好看下？
  - syq 广东省深圳市移动 1
    回复 2019年3月1日上午12:18 2层
    @Jack Cui 看错了，不好意思
Dejavu 天津市天津大学 2
回复 2019年4月17日上午10:38 4楼
你这个没把链表的方向反转啊
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年4月17日下午2:19 1层
  @Dejavu 已经反向了啊，你感觉哪里有问题？
  - Dejavu 天津市天津大学 2
    回复 2019年4月17日下午2:32 2层
    @Jack Cui 我的意思是比如1->2->3->4反转应该是4->3->2->1
    这道题返回的是向量这种解法可行
    但如果要求返回指向head的指针就不对了
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2019年4月17日下午3:54 3层
      @Dejavu 按照要求做题，这道题要求返回的，就是列表。你说的是：反转链表，剑指offer有另外一道题。
lanme2019 内蒙古电信 0
回复 2019年7月17日下午5:13 5楼
学习了膜拜大佬
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年7月17日下午7:24 1层
  @lanme2019 感谢支持~
Phil 新疆联通 0
回复 2020年10月3日下午9:38 6楼
博主，你题目打错了吧，返回的应该是一个列表，而不是链表吧？