题目描述
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
分析思路
这道题先采用双指针方法,首先定义一个cur,它指向head,还需要记录一个cur的pre,注意这里它初始化为nullptr。然后在一个循环中进行翻转,注意点:临时节点tmp,先赋值pre,再赋值cur。搞定!看下代码:
/**
* 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* cur = head;
ListNode* pre = nullptr;
while(cur){
// cur等于空的时候,循环结束。因此它只要有值就在遍历。
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
下面尝试一下递归写法。如何写呢?我们按照双指针的思路来看,首先我们写一个reverse函数,参数是cur和pre,初始的值是多少呢?与双指针中的一样,cur=head,pre=nullptr。即这行代码:return reverse(head, nullptr);
接下来是递归函数的终止条件,在双指针中cur==nullptr的时候结束循环,因此if (cur==nullptr) return pre
。函数中需要定义一个tmp节点存cur的next,翻转的代码仍然是cur->next = pre;
,然后调用自己,传入的参数是pre = cur, cur = tmp
,与双指针中的代码一模一样。因此递归函数写好了。
/**
* 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) {
// 迭代方法
return reverse(head, nullptr);
}
ListNode* reverse(ListNode*cur, ListNode* pre){
if(cur == nullptr) return pre; // 递归结束条件,就是cur是空
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(tmp, cur);
}
};