链表的逆置

题目一:

输入一个链表, 按链表从尾到头的顺序返回一个 ArrayList.

时间限制:

1 秒

空间限制:

32768K

解题思路:

这个题有三种想法:

• 使用栈先进后出的方式解决
• 使用向量逆置的方式
  可以使用 c++ 自带的 reverse 方法或者自己 swap 一下就行.
• 使用递归进行逆置
  我觉的这个才是这个题的考察点. 这个需要想清楚的就是递归到最后, 到达递归的零界点的时候是从后往前 return 回来的. 岂不是很完美的逆置吗. 并且想清楚, 后者的 return 的结果继续留在前者使用. 或者想想成每一次到递归时的值保留了下来(可以想象成缓存了下来), 当 return 到当前时, 也就是能继续往改次递归方法之下走时, 就使用缓存下来的值.

/**
*  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;
		stack<int> stk;
		ListNode *tmp = head;
                while (head != NULL) {
			stk.push(tmp->val);
			tmp = tmp->next;
		}
		while (!stk.empty()) {
			res.push_back(stk.top());
			stk.pop();
		}
		return res;
	}
/*方法一: 向量逆置*/
public:
	vector<int> printListFromTailToHead(ListNode* head) {
		vector<int> res;
		ListNode *tmp = head;
		while (tmp != NULL) {
			res.push_back(tmp.val);
			tmp = tmp->next;
		}
		// reverse(res.begin(), res.end()); C++自带的翻转函数
		int i = 0; 
		int j = res.size() - 1;
		while (i < j) {
			swap (res[i], res[j]);
		}
		return res;
	}
}
/*方法一: 递归逆置*/
public:
	vector<int> res;
	vector<int> printListFromTailToHead(ListNode* head) {
		ListNode *tmp = head;
		if (tmp != NULL) {
			if (tmp->next != NULL) {
				printListFromTailToHead(tmp->next);
			}
			res.push_back(tmp->val);
		}
		return res;
	}
}
​

小知识点 👍

push_back 和 insert 的区别
简单来说, 最大的不同是它们的功能和效率. push_back 会将一个新元素插在 vector 的尾部, insert 是可以允许选择一个新元素的位置的. 这个也是会对性能造成一定的影响. vector 元素在内存中移动只有在由于分配的内存太小需要增加其长度时才需要. 另一方面 insert 会移动新插入的新元素位置之后的所有元素. 这也是为什么通常情况下 insert 的效率要低于 push_back.
stack 的简单使用
栈先进后出就不多解释, 在 c++ 中 stack.empty() 是判断栈是否为空的. stack.top() 只是返回栈顶元素, 但是不做删除, 所以会结合 stack.pop().
如何理解递归
如果发现好的文章就不再多做累赘叙述, 引荐别人的好文如何很好的理解递归.