东莞企业网站推广运营,男女做受视频网站,正品手表网站,网站建设晋icp备链表内指定区间反转 题目描述思路一#xff08;暴力破解版#xff09;思路二#xff08;技巧反转版#xff09;思路三#xff08;递归魔法版#xff09;Thanks♪(#xff65;ω#xff65;)#xff89;谢谢阅读#xff01;#xff01;#xff01;下一篇文章见… 链表内指定区间反转 题目描述思路一暴力破解版思路二技巧反转版思路三递归魔法版Thanks♪(ω)谢谢阅读下一篇文章见 题目描述 根据题目描述大致思路比较顺畅需要使用链表的插入创建等内容。
思路一暴力破解版
首先找到第 m-1 个节点并记录然后开始反转遍历 m - n 链表节点 并依次头插到一个新链表中m-1节点 指向新链表 新链表尾指向 n1 个节点完成反转。
typedef struct ListNode node;struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {//如果 m n 不需要反转if (m n ) return head;// 定义新链表的头尾node* new NULL , *tail NULL;//定义 cur 来指向当前节点 方便遍历node* cur head;// 定义m-1节点 n1节点node* mnode NULL,*nnode NULL;//开始遍历int count 1;while(count m){//记录第 m-1 节点if(count m-1){mnode cur;}cur cur-next;count;}//开始反转while(count n){//记录第 n1个节点if(count n){nnode cur-next;}//每次创建新节点 拷贝node* newnode (node*)malloc(sizeof(node));newnode-val cur-val;//进行头插 new 为空则直接指向新节点 if(new NULL){new tail newnode;}else{newnode-next new;new newnode;}//迭代cur cur-next;count;}// 分情况讨论// 如果 mnode NULL 则标明 从头开始反转//直接将head newif (mnode NULL) {head new;}//反之将 新链表插入在mnode后else mnode-next new;// 新链表 指向nnodetail-next nnode;return head;
}运行效果
思路二技巧反转版
该版本使用了一个十分巧妙的算法不用额外开辟空间就能完成链表的反转。 通过从 m 到 n - 1的遍历 逐个将 temp 移到 prev 的后面 完成局部头插。
typedef struct ListNode node;
struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) {//定义一个 头结点 方便操作node* H (node*)malloc(sizeof(node));H-next head;//两个指针 分别指向 当前节点 和 前节点node* prev H,*cur head;// 遍历到 第m-1个节点for(int i 1;i m; i){prev cur;cur cur-next;}//开始反转for(int i m; in;i){// temp 指向 cur后一个节点node* temp cur-next;// 将temp移动到 prev 后// cur 移动到 temp 位置cur-next temp-next;temp-next prev-next;prev-next temp;}//返回return H-next;
}运行效果
思路三递归魔法版 思路来自牛客官方 我们来看看另一种分析如果m 1就相当于反转链表的前 n 元素如果 m ! 1我们把 head 的索引视为 1那么我们是想从第 m 个元素开始反转如果把 head.next 的索引视为1那相对于 head.next的反转的区间应该是从第 m−1 个元素开始的以此类推反转区间的起点往后就是一个子问题我们可以使用递归处理
终止条件 当m 1就可以直接反转前n个元素。
返回值 将已经反转后的子问题头节点返回给上一级。
本级任务 递归地缩短区间拼接本级节点与子问题已经反转的部分。从头开始往后去掉前面不反转的部分
ListNode node reverseBetween(head.next, m - 1, n - 1)而每次反转如果 n 1相当于只颠倒第一个节点如果不是则进入后续节点子问题因此反转过程也可以使用递归
终止条件 当n 1时只反转当前头节点即可。
返回值 将子问题反转后的节点头返回。
本级任务 缩短 n 进入子问题反转等子问题回到本级再反转当前节点与后续节点的连接。颠倒后续的节点直到n1为最后一个
ListNode node reverse(head.next, n - 1)具体做法
准备全局变量temp最初等于null找到递归到第n个节点时指向其后一个位置要将反转部分的起点即反转后的尾连接到这个指针。按照第一个递归的思路缩短子问题找到反转区间的起点将反转后的部分拼接到前面正常的后面。按照第二个递归的思路缩短终点的子问题从第n个位置开始反转反转过程中每个子问题作为反转后的尾都要指向temp。 typedef struct ListNode ListNode;ListNode* temp NULL;ListNode* reverse(ListNode* head, int n){//只颠倒第一个节点后续不管if(n 1){temp head-next;return head;}//进入子问题ListNode* node reverse(head-next, n - 1);//反转head-next-next head;//每个子问题反转后的尾拼接第n个位置后的节点head-next temp;return node;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {//从第一个节点开始if(m 1)return reverse(head, n);//缩减子问题ListNode* node reverseBetween(head-next, m - 1, n - 1);//拼接已翻转head-next node;return head;
}Thanks♪(ω)谢谢阅读
下一篇文章见
