如何用微信打开微网站,印刷 技术支持 东莞网站建设,兰州网络推广优化服务,wordpress自适应小说反转链表
给定一个单链表的头结点pHead#xff08;该头节点是有值的#xff0c;比如在下图#xff0c;它的val是1#xff09;#xff0c;长度为n#xff0c;反转该链表后#xff0c;返回新链表的表头。
如当输入链表{1,2,3}时#xff0c;经反转后#xff0c;原链表变…反转链表
给定一个单链表的头结点pHead该头节点是有值的比如在下图它的val是1长度为n反转该链表后返回新链表的表头。
如当输入链表{1,2,3}时经反转后原链表变为{3,2,1}所以对应的输出为{3,2,1}。以上转换过程如下图所示 示例
输入{1,2,3}
返回值{3,2,1}好久好久没有刷题了这一年大多在写Shell脚本或者Python脚本去了已经忘记自己是C起家的了好几天前大页表吴同学找了两个题目说有意思让我试一下害当天晚上没做出来有时间了再看这题目其实就是头插法尾插法是正序头插法就是反转了代码附上关键是第二题。
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include cstddef
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 * return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs NULL;ListNode* Next head-next;ListNode* Cur head;while(Cur){Cur-next Rs;Rs Cur;Cur Next;Next Next-next;}return Rs;}
};链表内指定区间反转
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。 这个题目首先我的想法就是把第一题反转的函数用上然后把只需要截断反转再连接就可以了。我们使用示例{12345}24。
第一种思路
首先是找到需要反转的区间链表
ListNode* dummyNode new ListNode(-1);
dummyNode-next head;ListNode* pre dummyNode;
for(int i0;im-1;i){pre pre-next;
}ListNode* rightNode pre ;
for(int i0;in-m1;i){rightNode rightNode-next;
}ListNode* leftNode pre-next;//leftNode {2345}
ListNode* cur rightNode-next;//后置链表 cur {5}//截断链表
pre-nextNULL;//前置链表截断 pre {1}
rightNode-nextNULL;//后置链表截断 leftNode {234}反转函数
ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs NULL;ListNode* Next head-next;ListNode* Cur head;while(Cur){Cur-next Rs;Rs Cur;Cur Next;Next Next-next;}return Rs;
}得到反转后的区间后前置部分直接链接后置部分通过遍历到反转区间链表的最后一个元素指向最后一部分。
ListNode* mid ReverseList(leftNode);//mid {432}pre-next mid;
while (mid -next)mid mid - next;
mid -next cur;
return dummyNode-next;完整代码
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include ios
#include iostream
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类* param m int整型* param n int整型* return ListNode类*/ListNode* ReverseList(ListNode* head) {// write code hereListNode* Rs NULL;ListNode* Next head-next;ListNode* Cur head;while(Cur){Cur-next Rs;Rs Cur;Cur Next;Next Next-next;}return Rs;}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode new ListNode(-1);dummyNode-next head;ListNode* pre dummyNode;for(int i0;im-1;i){pre pre-next;}ListNode* rightNode pre ;for(int i0;in-m1;i){rightNode rightNode-next;}ListNode* leftNode pre-next;ListNode* cur rightNode-next;pre-nextNULL;rightNode-nextNULL;ListNode* mid ReverseList(leftNode);pre-next mid;while (mid -next)mid mid - next;mid -next cur;return dummyNode-next;}
};第二种思路
第二种思路就是反转函数返回一个链表有点多此一举只需要在反转函数里对链表进行操作即可。 反转函数
void ReverseList(ListNode* head) {// write code hereListNode* Rs NULL;ListNode* Next head-next;ListNode* Cur head;while(Cur){Cur-next Rs;Rs Cur;Cur Next;Next Next-next;}
}反转后
//反转前 leftNode {234} rightNode {4}
ReverseList(leftNode);
//反转后 leftNode {2} rightNode {432}
pre-next rightNode;
leftNode-next cur;
return dummyNode-next;完整代码
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include ios
#include iostream
using namespace std;
class Solution {public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param head ListNode类* param m int整型* param n int整型* return ListNode类*/void ReverseList(ListNode* head) {// write code hereListNode* Rs NULL;ListNode* Next head-next;ListNode* Cur head;while(Cur){Cur-next Rs;Rs Cur;Cur Next;Next Next-next;}}ListNode* reverseBetween(ListNode* head, int m, int n) {// write code hereListNode* dummyNode new ListNode(-1);dummyNode-next head;ListNode* pre dummyNode;for(int i0;im-1;i){pre pre-next;}ListNode* rightNode pre ;for(int i0;in-m1;i){rightNode rightNode-next;}ListNode* leftNode pre-next;ListNode* cur rightNode-next;pre-nextNULL;rightNode-nextNULL;ReverseList(leftNode);pre-next rightNode;leftNode-next cur;return dummyNode-next;}
};链表介绍
链表Linked List是一种线性数据结构其中的元素通常称为节点按顺序排列每个节点包含两部分信息存储数据的部分和指向下一个节点的指针或引用。链表中的每个节点通过指针连接在一起因此它不需要在内存中连续存储。链表有几种常见的形式
单向链表Singly Linked List每个节点只包含一个指向下一个节点的指针链表是单向的无法向后遍历。双向链表Doubly Linked List每个节点包含两个指针一个指向下一个节点另一个指向前一个节点因此可以双向遍历。循环链表Circular Linked List链表的最后一个节点指向链表的第一个节点形成一个环。
链表的优点
动态内存分配链表不需要预先定义大小可以根据需要动态增长或缩小。插入和删除操作链表的插入和删除操作可以在常数时间内完成特别是对于已知位置的节点。
链表的缺点
随机访问由于链表的元素不在连续的内存位置因此不能像数组一样通过索引进行随机访问必须从头节点开始遍历。
链表广泛应用于实现队列、栈以及某些复杂数据结构如图和哈希表的底层实现。
