从尾到头打印链表

1. 题目描述

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

2. 思路

• 递归：如果下一个节点不为空，先打印下一个，然后打印本节点
• 栈：后进先出

3. 实现

3.1. 递归

• java

public class 从尾到头打印链表
{
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode)
    {
        ArrayList<Integer> res = new ArrayList<>();
        //检查参数
        if (listNode == null)
        {
            return res;
        }

        //递归：如果下一个节点不为空那么先打印下一个节点
        this.printListFromTailToHeadRecursively(listNode, res);
        return res;
    }

    private void printListFromTailToHeadRecursively(ListNode listNode, ArrayList<Integer> res)
    {
        if (listNode.next != null)
        {
            this.printListFromTailToHeadRecursively(listNode.next, res);
        }

        res.add(listNode.val);
    }
}

• go

//递归
//空间：
//时间：
func printListFromTailToHead(head *ListNode) []int {

	if head == nil {
		return nil
	}

	res := make([]int, 0)

	printListFromTailToHeadRecur(&res, head)

	return res
}

func printListFromTailToHeadRecur(res *[]int, n *ListNode) {
	if n == nil {
		return
	}

	printListFromTailToHeadRecur(res, n.Next)
	*res = append(*res, n.Val)
}

3.2. 栈

//数组后反转
//空间：
//时间：
func printListFromTailToHead2(head *ListNode) []int {

	if head == nil {
		return nil
	}

	res := make([]int, 0)

	node := head
	for node != nil {
		res = append(res, node.Val)
		node = node.Next
	}

	reverse(res)

	return res
}

func reverse(s []int) []int {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
	return s
}

4. 参考

• 从尾到头打印链表_牛客网
• LCR 123. 图书整理 I - 力扣（LeetCode）