单链表的逆置

方法一：迭代逆置

在上一篇文章的基础上添加Reverse()方法。

//列表逆置
public void Reverse() {
    if (Head == null || Head.Next == null)  //空或者只有一个元素不用逆置
        return;
    Node<T> pre, cur, rear;
    pre = Head;
    cur = Head.Next;
    while (cur!=null)
    {
        rear = cur.Next;
        cur.Next = pre;
        pre = cur;
        cur = rear;
    }
    //以下两步，很重要
    Head.Next = null;   //这一步会使新的尾节点的链域置空
    Head = pre;   //head指针指向新的一头
}

方法二：递归逆置

//列表逆置 递归
void reverseWithRecursion(Node<T> h, Node<T> c)    //递归逆置
{
    if (c.Next == null)   //最后一个元素是递归终止条件
    {
        Head = c; //此刻的C为最后一个，将其置为头节点。
        return;
    }
    Node<T> r = c.Next;
    reverseWithRecursion(h, r);
    r.Next = c; //让本次循环的r的下一个指向c，相当于反转
    //cur->next = NULL;    //句一，这一句可以注释掉
}
public void reverse()
{
    if (Head == null || Head.Next == null)   //为空或只有一个元素就结束 
         return;
    Node<T> cur = Head;
    reverseWithRecursion(Head, cur);
    cur.Next = null;    //句二，这一句可以注释掉，不过句一和句二必须保留一句
}