题解 | #反转链表#

算法总结实践第一题——反转链表

首先寻找终止的条件：pHead == NULL ||pHead->next == NULL

pHead指向空或者pHead的next指向空

因为在这两种情况下，反转的结果还是自己，因此作为终止的条件。

不断通过递归调用，直到最后一个节点符合终止条件，也就是我们要返回的反转链表的表头结点。

返回cur到调用该函数的地方，如果该链表总共有五个节点，即此时PHead指向第四个节点。

将4->next(5)->next=4，也就是创建一个5->4的连接，再讲4->next=NULL，就完成了这两个节点的反转。

再将cur返回给上一层。

*自我认为做该类题目还是要比较熟悉递归函数的调用和过程，不然会越来越乱QAQ。

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
#include <cstddef>
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if(pHead == NULL ||pHead->next == NULL)
		{
			return pHead;
		}
		ListNode *cur =ReverseList(pHead->next); 
		pHead->next->next=pHead;
		pHead->next=NULL;
		return cur;
    }
};