}

1.单链表反转

这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：
算法 1：我们需要额外的两个变量来存储当前节点 curr 的下一个节点 next、再

下一个节点 nextnext：
public static Link ReverseLink1(Link head)
{
    Link curr = head.Next;
    Link next = null;
    Link nextnext = null;
    //if no elements or only one element exists
    if (curr == null || curr.Next == null)
    {
        return head;
    }
    //if more than one element
    while (curr.Next != null)
    {
        next = curr.Next;       //1
        nextnext = next.Next;   //2
        next.Next = head.Next;  //3
        head.Next = next;       //4
        curr.Next = nextnext;   //5
    }
    return head;
}

算法的核心是 while 循环中的 5 句话

我们发现，curr 始终指向第 1 个元素。

此外，出于编程的严谨性，还要考虑 2 种极特殊的情况：没有元素的单链表，

以及只有一个元素的单链表，都是不需要反转的。

算法 2：自然是递归

如果题目简化为逆序输出这个单链表，那么递归是很简单的，在递归函数之
后输出当前元素，这样能确保输出第 N 个元素语句永远在第 N+1 个递归函数

之后执行，也就是说第 N 个元素永远在第 N+1 个元素之后输出，最终我们先

输出最后一个元素，然后是倒数第 2 个、倒数第 3 个，直到输出第 1 个：
public static void ReverseLink2(Link head)
{
    if (head.Next != null)