链表反转

链表反转的思路：
1.利用栈后进先出的特性，将链表的每个节点都Push进栈，然后再Pop出栈，保存进链表，实现反转。

2利用递归，调用到尾端的节点，回溯保存进链表，实现反转。

public class ListNode
{
  public int val;
  public ListNode next;
  public ListNode(int x)
  {
      val = x;
  }
}

public List<int> printListFromTailToHead(ListNode listNode)
{
    // 利用栈版本
    Stack<int> _stack = new Stack<int>();
    while (listNode != null)
    {
        _stack.Push(listNode.val);
        listNode = listNode.next;
    }
    List<int> newList = new List<int>();

    while (_stack.Count != 0)
    {
        newList.Add(_stack.Pop());
    }
    return newList;
    //-------------------------------------------------------------------------------
    //递归版本
    if (listNode!=null)
    {
        if (listNode.next!=null)
        {
            printListFromTailToHead(listNode.next);
        }
        newList.Add(listNode.val);
    }
    return newList;
}