链表的逆置

whoami Clowns Laughing @You 本文由博客端 https://www.reyren.cn 主动推送
本贴最后更新于 821 天前,其中的信息可能已经东海扬尘

题目一:

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

时间限制:

1 秒

空间限制:

32768K

解题思路:

这个题有三种想法:

/**
*  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().
如何理解递归
如果发现好的文章就不再多做累赘叙述, 引荐别人的好文如何很好的理解递归.


2 回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone
    作者

    都是 log(n)

  • 其他回帖
  • someone

    三种方法的效率比较可以说一下吗