剑指offer学习笔记——链表2：单链表的翻转（非递归&递归）

对应于剑指offer代码鲁棒性面试题16——反转链表：

题目：输入一个链表，反转链表后，输出反转之后链表的头结点。

求解思路：

有非递归与递归两种解法：

1、如果用非递归，为了防止反转一个结点之后链表断掉，我们必须记录当前结点cur，当前结点之前的节点pre，以及当前结点之后的节点post。

2、如果使用递归，我们就假设当前结点之后的都已经反转好了。仅仅需要将当前结点之后的结点（post）连到当前结点，当前结点指向NULL即可。

注意！！！为保证鲁棒性，最好事先想好特殊测试样例：

1）输入的链表表头为NULL

2）输入的链表只有一个结点

3）输入的链表有多个结点

具体代码如下：

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/

class Solution {
public:
    //方法一：非递归的思路
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)
           return NULL;
        ListNode *pre = NULL,*cur = pHead,*post = NULL;
        while(cur!=NULL)
        {
            post = cur->next;
            cur->next = pre;
            pre = cur;
            cur = post;
        }
        return pre;
    }
    
    
    //方法二：递归思路
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)
            return NULL;
        return RecursionReverse(pHead);
        
    }
    ListNode* RecursionReverse(ListNode* pNode)
    {
        if(pNode->next==NULL)
            return pNode;
        ListNode* pHead = RecursionReverse(pNode->next);
        pNode->next->next = pNode;
        pNode->next = NULL;
        return pHead;
    }
};