面试题5：从尾到头打印链表(剑指Offer)

题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

1.遍历，反转

public int[] ReversePrint(ListNode head)
{
    var reData = new List<int>();
    if (head == null)
        return reData.ToArray();
    while (head != null)
    {
        reData.Add(head.val);
        head = head.next;
    }
    reData.Reverse();
    return reData.ToArray();
}

2.栈

public int[] ReversePrint(ListNode head)
{
    var stack=new Stack<int>();
    while (head!=null)
    {
        stack.Push(head.val);
        head = head.next;
    }
    var arr = new int[stack.Count];
    var index = 0;
    while (stack.Count>0)
    {
        arr[index++] = stack.Pop();
    }
    return arr;
}

3.递归

public int[] ReversePrint(ListNode head)
{
    if (head == null) return new int[0];
    List<int> ls = new List<int>();
    ls.Add(ReversePrint(head, ls));
    return ls.ToArray();
}
public int ReversePrint(ListNode head, List<int> ls)
{
    if (head.next == null) return head.val;
    ls.Add(ReversePrint(head.next, ls));
    return head.val;
}