网站建设的重难点分析,哈尔滨企业建站系统,网站建设中 敬请期待,商丘seo题目描述
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a;
输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1]示例 2#xff1a;
输入#xff1a;head [1,2]
输出#xff1a;[2,1]示例 3#xf…题目描述
给你单链表的头节点 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初始的值是多少呢与双指针中的一样curheadprenullptr。即这行代码return reverse(head, nullptr);
接下来是递归函数的终止条件在双指针中curnullptr的时候结束循环因此if (curnullptr) 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);}
};
