从尾到头打印链表
来源： https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035
描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]，0 <= 链表长度 <= 1000
示例1
1
2
|
输入：{1,2,3}
返回值：[3,2,1]
|
示例2
1
2
|
输入：{67,0,24,58}
返回值：[58,24,0,67]
|
思路
(1) 一开始很多人拿到这个题，很自然的想到是否直接把链表中的链接结点的指针反转过来，改变链表的方向，那么很自然的就实现了从头到尾的输出了。然而这个方法会改变原来链表的结构， 是否会允许我们在打印链表时候改变链表的结构？这取决于面试官的需求。
(2) 一般是不允许的，打印时不能修改原有链表的结构；那么解决这个链表肯定是需要遍历链表，当前遍历是从头到尾的顺序，要求的顺序是 从尾到头。也就是说 第一个节点最后一个输出， 这不就是 “后进先出"么， 我们立即想到用栈来实现这个顺序。
每经历一个结点的时候，就把它压入到一个栈中，当遍历到整个链表后，再从栈顶开始逐个输出结点的值，此时输出结点的顺序已经反转过来了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 定义链表结构
type ListNode struct {
Val int
Next *ListNode
}
// 打印链表
func (l *ListNode) readLink() {
var result []int
for l != nil {
result = append(result, l.Val)
l = l.Next
}
fmt.Println(result)
}
|
ps: my ugly code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
package main
import . "nc_tools"
import "errors"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @return int整型一维数组
*/// 实现一个栈
type Stack []interface{}
func (stack *Stack) Push(value interface{}) {
*stack = append(*stack, value)
}
func (stack Stack) Top() (interface{}, error) {
if len(stack) == 0 {
return nil, errors.New("Out of index, len is 0")
}
return stack[len(stack)-1], nil
}
func (stack *Stack) Pop() (interface{}, error) {
theStack := *stack
if len(theStack) == 0 {
return nil, errors.New("out of index, len is 0")
}
value := theStack[len(theStack)-1]
*stack = theStack[:len(theStack)-1]
return value, nil
}
func (stack Stack) IsEmpty() bool {
return len(stack) == 0
}
func printListFromTailToHead( head *ListNode ) []int {
// write code here
var nodeStack Stack
var pNode = new(ListNode)
pNode = head
for pNode != nil {
nodeStack.Push(pNode)
pNode = pNode.Next
}
var res = make([]int, len(nodeStack))
index := 0
for !nodeStack.IsEmpty() {
top, _ := nodeStack.Top()
node := top.(*ListNode)
res[index] = node.Val
_, _ = nodeStack.Pop()
index++
}
return res
}
|
既然都已经用栈来实现了这个函数，我们知道递归本质上就是一个栈结构；很自然的想到了用递归来实现，要想实现反过来输出链表，每访问一个结点的时候，先递归输出它后面的结点，再输出该结点自身， 这样链表的输出结果就反过来了；
1
2
3
4
5
6
7
8
|
func printListFromTailToHead_Recursively(head *ListNode) {
if head != nil{
if head.Next != nil{
printListFromTailToHead_Recursively(head.Next)
}
fmt.Println(head.Val)
}
}
|
上面用递归实现的看起简单， 但是是不是就没什么问题？ 答案是否定的；
当链表非常长的时候，就会导致函数的调用层级很深，进而有可能导致函数的调用栈溢出；相比起来，显式的用栈基于循环实现的代码的鲁棒性要更好一些；
测试用例
- 功能测试（输入的链表有多个节点，输入的链表只有一个节点）
- 特殊输入的测试 （输入的链表头结点的指针为nil）
本题考点
- 考察单链表的理解和编程能力；
- 考察对循环，递归和栈3个相互关联的概念和理解；
高手解法与赏析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/*
a.实际上是一种往列表头部插入的一个思路了；
b.ArrayList 中有个方法是 add(index,value)，可以指定 index 位置插入 value 值
所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置，最后输出 listNode 即可得到逆序链表；
c.复杂度
时间复杂度：O(n)
空间复杂度：O(n)
*/
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
ListNode tmp = listNode;
while(tmp!=null){
list.add(0,tmp.val);
tmp = tmp.next;
}
return list;
}
}
|