带有头节点的单链表反转

题目描述：
给定一个带有头节点的单链表，输出逆序反转后的链表
分析：链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可，注意要防止处理过程中导致链表成为孤岛。
具体的分析过程如下：

代码如下：

//单链表的转置,循环方法
Node* reverseByLoop(Node *head) {
    if(head == NULL || head->next == NULL)
        return head;
    Node *pre = NULL;
    Node *next = NULL;
    while(head != NULL) {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。
前面非递归方式是从链表开始往后依次处理，而递归方式则恰恰相反，它先循环找到最后面指向的节点，然后再更新每一个node的next值 ，实现链表的反转。而newhead 的值没有发生改变，为该链表的最后一个结点，所以反转后，我们可以得到新链表的head。
具体过程如下图所示：
代码：

//单链表的转置,递归方法
Node* reverseByRecursion(Node *head) {
    //第一个条件是判断异常，第二个条件是结束判断
    if(head == NULL || head->next == NULL)
        return head;
    Node *newHead = reverseByRecursion(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;//返回新链表的头指针
}

参考：
http://wuchong.me/blog/2014/03/25/interview-link-questions/
http://blog.csdn.net/fx677588/article/details/72357389
https://www.cnblogs.com/kubixuesheng/p/4394509.html