Print Linked List from Tail to Head

1. Problem Description

Given a linked list, return an ArrayList containing its values from tail to head.

2. Approach

• Recursion: if the next node is not nil, output the next node first and then the current node
• Stack: last in, first out

3. Implementation

3.1. Recursion

• java

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

        // Recursion: if the next node is not nil, print the next node first
        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

// Recursion
// Space:
// Time:
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. Stack

// Store in an array and then reverse it
// Space:
// Time:
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. References

• Print a Linked List from Tail to Head - NowCoder
• LCR 123. Book Organization I - LeetCode