【408DS算法题】016基础-倒序输出单链表的结点值

Index

• • 题目
  • 分析实现
  • • 总结

题目

给定单链表的头结点，倒序输出单链表的结点值。

分析实现

要倒序输出链表结点值，首先可以想到的是先将链表的结点值存储到数组中，然后利用数组随机访问的特性进行倒序输出。

如果考虑其它思路的话，还可以使用栈来代替数组——将链表元素依次入栈，然后再不断出栈，就得到了逆序的输出。而再进一步去想，递归也是利用了栈的思想，本文的实现方式就算利用了递归的思想（使用栈和递归相对于使用数组，时间复杂度和空间复杂度并不会优化——递归时的递归栈也会占用存储空间，但使用递归的写法可以让代码更加简洁优雅）。

具体实现如下：

void printReverse(LNode *cur) {
	// 递归基
	if (cur == NULL) {
		return;
	}
	// 首先递归输出后续节点
	printReverse(cur->next);
	// 然后输出当前节点
	cout << cur->val << ' ';
}

总结

本篇文章使用递归函数实现了单链表结点值的逆序输出。单链表的逆序输出本身不是一个很难的题目，但本题还可以作为学习递归函数的一个小练习，递归函数的代码往往很简洁却并不容易书写和理解，如果需要熟练掌握需要多加练习。