剑指Offer:丛尾到头打印链表

题目描述

输入一个链表,从尾到头打印链表每个节点的值。

分析

由于链表的遍历只能是从头到尾,可输出的顺序是丛尾到头。也就是说,第一个遍历的节点最后一个输出。这是典型的“后进先出”,我们可以用栈来实现这种顺序。当然我们也可以用递归(递归代码看起来会很简洁,但当链表的节点非常长的时候,就会导致函数调用的层级很深,效率不高而且有可能会导致栈溢出)

下面分别给出这两种实现

栈实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
struct ListNode{
int m_nKey;
ListNode* m_pNext;
}
*/

public void printListFromTailToHead(ListNode* pHead){

std::stack<ListNode*> nodes;

ListNode* pNode = pNode;
while (pNode != nullptr){
nodes.push(pNode);
pNode = pNode->m_pNext;
}

while (!nodes.empty()){
pNode = nodes.top();
print("%d\t",pNode->m_nKey);
nodes.pop();
}
}
递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> array = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode == null) return array;
printListFromTailToHead(listNode.next);
array.add(listNode.val);
return array;
}
}

我们也可以先将链表翻转,再遍历输出。
具体请参考剑指Offer:链表翻转