给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。 数据范围： 要求：空间复杂度 ，时间复杂度 。

以下是解答：

可以使用迭代或递归的方法反转单链表。

迭代方法：
首先设pre指向null，cur指向pHead，然后用一个while循环，每次循环中将cur的next指向pre，然后让pre和cur都向后移动一位。当cur为null时，返回pre。

递归方法：
先考虑pHead后面的节点已经被反转了，现在需要反转pHead的next这个节点，并将它的next指向pHead。此时新链表的头节点是pHead的next。再返回新链表的表头即可。

以下是代码示例：

迭代方法：

class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};

递归方法：

class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
};