题解 | #反转链表#

递归：

函数返回的是反转后的头节点，即固定为原链表中最后一个节点，所以当前函数的返回值应该与递归函数的返回值是一样的。

反转之后应该由原链表中pHead->next指向的节点指向pHead，同时考虑pHead是反转后尾部的情况，应该把pHead->next置为nullptr。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if (!pHead || !pHead->next) return pHead;
		ListNode* newhead = ReverseList(pHead->next);
		pHead->next->next = pHead;
		pHead->next = nullptr;
		return newhead;
    }
};

迭代：

设置bef与now两个节点，now指向当前需要反转的节点，bef指向原链表中now的上一个节点，每次迭代就将now->next设置为bef，由于设置之后会丢失now->next原来的值，所以需要事先用nxt存储now->next原来的值，并在之后赋值给now，now的值赋给bef实现右移。

在循环的最后，now是nullptr，而bef指向now在原链表中的上一个节点，即为原链表的尾部，也是新链表的头部，所以返回bef。

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		ListNode* bef = nullptr, *now = pHead;
		while (now) {
			ListNode* nxt = now->next;
			now->next = bef;
			bef = now;
			now = nxt;
		}
		return bef;
    }
};