给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
双指针法+辅助结点:
AC代码
/**
* 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) {
//依次处理 每次仅需要处理一对结点的连接关系
ListNode* pre = nullptr; //也可以理解为前哨结点
ListNode* cur = head; //此时pre 与 cur就构成了一对待处理的结点
ListNode* tmp; //辅助结点 用处保留下一个待处理的结点
while(cur!=nullptr){
tmp = cur->next;
cur->next = pre;
//下一对要处理的结点
pre = cur;
cur = tmp;
}
return pre;
}
};
递归解法,思路本质上与上面的是相同的:
AC代码
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur){
if(cur == nullptr) return pre;
ListNode* tmp = cur->next;
cur -> next = pre;
//更新
//pre = cur;
//cur = tmp;
return reverse(cur, tmp);
}
ListNode* reverseList(ListNode* head) {
return reverse(nullptr, head);
}
};