力扣——链表：翻转链表

1、迭代，将指向反转

使用新建的next指针，先将当前元素的后面的元素存储下来

改变当前元素的指向，然后更新当前元素和前一个元素的值

循环的条件是当前元素是否为空，因此循环结束时，curr应该是空的，因此返回应该是返回pre，也就是当前元素的前一个

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr)return nullptr;ListNode* pre=nullptr;ListNode* curr=head;ListNode* next=nullptr;while(curr){next=curr->next;curr->next=pre;pre=curr;curr=next;}return pre;}
};

2、递归

若链表为空或仅有一个节点，则直接返回头节点（无需反转）

递归地反转以头节点下一个节点开始的子链表，该递归调用返回反转后子链表的新头节点

在递归返回后，将当前头节点的下一个节点的`next`指针指向当前头节点，实现局部反转

然后将当前头节点的next置为空，断开与原链表的连接，避免成环

最后，递归过程始终返回子链表反转后的新头节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
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;}
};