从尾到头打印链表 之 “C++代码＋思路解析 ”

下一篇 从尾到头打印链表 (第二种情况 允许原地打印链表)

希望我的文字始终给您带来画面感。

其实做算法题的过程也是在考验我们的大脑日常解决问题的能力，懂不懂得将生活中碰到的难题拆分，一一解决。

今日感悟：

做算法题不要过分依赖于自己旧的的知识库，独立的把它看做一道新鲜的算法题。千万不要一碰到陌生的知识点就丢失信心。做新的算法题一定会涉及到不熟悉的数据结构知识和语法问题，把它当做工具先使用，有时间的话再去了解它是什么，不要在认识它的本质上浪费一分一秒的时间。

题目开始咯！

  题目描述：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

//这里敲黑板，千万注意：我们做算法题 ，最基本的也是最关键的题目一定要 理解准确。这道题涉及到允不允许原地修改链表，所以分为以下两种情况。

 第一种情况：不允许原地修改链表，如果不允许原地修改链表，
 那么可以利用栈后进先出的特点，遍历链表，逐个将链表元素放入栈中，
 然后依次弹出栈顶元素并打印。

代码实现部分：

//5月8日
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;
		//我写代码定义一般先不写，后面需要用到就把它加上。
		stack<int> sta;    
		ListNode* p = head;//指针就记着在内存里面给这个变量p分配一块地址，跟变量一样使用。
		while ( p )
		{
			sta.push( p->val );//循环里面最关键的是push这个动作
			p = p->next;
		}
		while ( !sta.empty() )
		{
			int a = sta.top();
			sta.pop();
			res.push_back(a);
		}

		return res;
   }
};

思路解析部分：

我不知道大家的写算法思路是思维习惯和先后顺序是怎样的，我会习惯将代码拆分成小的代码块进行 ，再进行逻辑组合安装。当然这里无法评判哪种一定是正确的，这里我想分享一下：我个人认为最快的写代码顺序。

第一步：我会先搞清楚题目 ，需要我给它一个什么，定下来整体的框架。

比如这道题它要我给它返回一个 数组。一个装着链表中倒序值的数组。那么 返回值类型 和 返回语句
心里就有个概念了。还要搞清楚我们这道题需要的数组选择用静态的还是动态，动态就用vector。

那第一步函数整体的框架就出来咯！

vector< int > printListFromTailToHead（..........）{
vector< int > res;
................................
return res;
}

第二步：我会把参数定下来，进到函数体首先就检查参数合不合法。

加入 if 语句检验参数 链表指针 head 是否为空。

vector< int > printListFromTailToHead（ ListNode* head ）{
vector< int > res;
//加入这块代码检验参数。
if( !head )
{
 return res;
}
................................
return res;
}

第三步：给框架里面填上语句块。发挥（ if，while，for…）语句的作用,语句其实就是思考逻辑的实现。

这道题的逻辑就是把链表的数值一个一个倒进栈里，再从栈一个一个倒入新的容器里，拿到这个容器就OK了。

1 填入 这块代码，使用while 语句，把链表里的值一个一个推到栈里。

vector< int > printListFromTailToHead（ ListNode* head ）{
vector< int > res;
if( !head )
{
 return res;
}
//加入这块代码向栈里推数值
...............................//这里要加定义
while ( p )
{
    sta.push( p->val );//循环里面最关键的是push这个动作
	p = p->next;
}

................................
return res;
}

2 再填入一块代码，继续使用while语句，把栈里的值一个一个弹出来，再一个一个推到容器里面。

vector< int > printListFromTailToHead（ ListNode* head ）{
vector< int > res;
if( !head )
{
 return res;
}
//加入这块代码向栈里推数值
...............................//这里要加定义
while ( p )
{
    sta.push( p->val );//循环里面最关键的是push这个动作
	p = p->next;
}
//加入这块代码，把栈里的值一个一个弹出来，再一个一个推到容器里面。
while ( !sta.empty() )
		{
			int a = sta.top();
			sta.pop();
			res.push_back(a);
		}
return res;
}

第四步：抠细节，扣语句块里的细节，没定义的变量要给定义。对象要使用什么函数来实现，组装起来。

1 给对象加上定义。

while ( p )
{
    sta.push( p->val );//循环里面最关键的是push这个动作
	p = p->next;
}

while语句循环检验的这个指针p ，要在前面加上定义。
sta 是一个栈变量，它是一个数据的临时存放容器，继续补上定义。

ListNode* p = head;

stack<int> sta;  

这就知道了p指向的是传进来的链表head的头结点，sta是一个栈变量。

2 使用函数 top() ，pop()， push_back（），也就是组装动作。

while ( !sta.empty() )
		{
			int a = sta.top();
			sta.pop();
			res.push_back(a);
		}

总结：

我做算法题是先搞清楚题意，安排总框架，然后把解决办法拆分成一个个步骤，再把每个步骤落实到代码块，最后填充细节。

这样可以保证算法题做下来的整个过程中我们的整个思路是清晰的，不会让看似复杂的算法在我们的大脑中留下坏印象，使我们丧失兴趣。

其实做算法题的过程也是在考验我们的大脑日常解决问题的能力，懂不懂得将生活中碰到的难题拆分，一一解决。

下一篇 从尾到头打印链表(第二种情况 允许原地打印链表)