定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
方法一：双指针
具体过程如下：
假设链表为 1→2→3→∅，我们想要把它改成∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(1)。
ListNode* reverseList(ListNode* head) { if (head == nullptr) { return nullptr; } ListNode *prev = nullptr; ListNode *curr = head;//双指针解法 while (curr) { ListNode *next = curr->next; //保存一下 cur的下一个节点，因为接下来要改变cur->next curr->next = prev; //翻转操作 prev = curr; //更新pre 和 cur指针 curr = next; } return prev; }
方法二：递归
复杂度分析
- 时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。
- 空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。
ListNode* reverseList(ListNode* head) { if (!head || !head->next) { return head; } ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead; }
