从尾到头打印链表-数据结构与算法(下)

当前位置:　首页>> 技术小册>> 数据结构与算法(下)

### 题目描述
输入一个链表，按链表值从尾到头的顺序返回一个 `ArrayList`。

### 解法
#### 解法一【推荐】
遍历链表，每个链表结点值 `push` 进栈，最后将栈中元素依次 `pop` 到 `list` 中。
```java
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

/**
 * @author bingo
 * @since 2018/10/28
 */
public class Solution {
    /**
     * 从尾到头打印链表
     * @param listNode 链表头节点
     * @return list
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()) {
            res.add(stack.pop());
        }
        
        return res;
    }
}
```

#### 解法二【不推荐】
利用递归方式：
- 若不是链表尾结点，继续递归；
- 若是，添加到 `list` 中。

这种方式不推荐，当递归层数过多时，容易发生 `Stack Overflow`。

```java
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;

/**
 * @author bingo
 * @since 2018/10/28
 */
public class Solution {
    /**
     * 从尾到头打印链表
     * @param listNode 链表头结点
     * @return list
     */
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if (listNode == null) {
            return res;
        }
        
        addElement(listNode, res);
        return res;
        
    }
    
    private void addElement(ListNode listNode, ArrayList<Integer> res) {
        if (listNode.next != null) {
            // 递归调用
            addElement(listNode.next, res);
        }
        res.add(listNode.val);
    }
}
```

### 测试用例
1. 功能测试（输入的链表有多个结点；输入的链表只有一个结点）；
2. 特殊输入测试（输入的链表结点指针为空）。

该分类下的相关小册推荐：

编程之道-算法面试(上)

业务开发实用算法精讲

数据结构与算法(上)

数据结构与算法(中)

算法面试通关 50 讲

编程之道-算法面试(下)

数据结构与算法之美