株洲网站开发公司电话,移动网站开发基础知识,公众号如何开通,wordpress文章页跳转空白一.题目要求
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
二.题目难度
简单
三.输入样例
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1]
示例 2#xff1a; 输入#xff1a;head [1,2…一.题目要求
给你单链表的头节点 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
进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
四.解题思路
解法1尾插法 解法2递归
五.代码实现
迭代
/*** 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 *p head;ListNode *q head;ListNode *r q;if(head NULL) return NULL;while(p-next ! NULL) p p-next;ListNode *back p;while(r ! back){r q-next;q-next p-next;p-next q;q r;}return back;}
};递归看的评论
class Solution {
public:ListNode* reverseList(ListNode* head) {// 链表为空时直接返回链表不为空则到返回最后一个节点if(!head || !head-next) {return head;}// newHead先指向最后一个节点注意此时参数是倒数第二个节点// 这一步很精妙每一次newHead都是指向空指针链表为空或保留在原链表中的最后一个节点链表不空作用就是返回新的头结点ListNode* newHead reverseList(head-next);// 最后一个节点指向倒数第二个节点head-next-next head;// 倒数第二个节点的下一节点置空。此时倒数第三个节点仍指向倒数第二个节点下一次递归中将倒数第二个节点下一节点指向倒数第三个节点不断重复这一过程head-next nullptr;return newHead;}
};六.题目总结
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;}
};
