【刷题】牛客

2024-07-07 18:14| 来源: 网络整理| 查看: 265

链表内指定区间反转题目描述思路一（暴力破解版）思路二（技巧反转版）思路三（递归魔法版）Thanks♪(･ω･)ﾉ谢谢阅读！！！下一篇文章见！！！题目描述

根据题目描述，大致思路比较顺畅，需要使用链表的插入，创建等内容。

思路一（暴力破解版）首先找到第 m-1 个节点并记录然后开始反转遍历 m - n 链表节点，并依次头插到一个新链表中m-1节点指向新链表，新链表尾指向 n+1 个节点完成反转。代码语言：javascript复制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节点 n+1节点 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 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 = new if (mnode == NULL) { head = new; } //反之将新链表插入在mnode后 else mnode->next = new; // 新链表指向nnode tail->next = nnode; return head; }

运行效果：

思路二（技巧反转版）

该版本使用了一个十分巧妙的算法，不用额外开辟空间就能完成链表的反转。

通过从 m 到 n - 1的遍历逐个将 temp 移到 prev 的后面完成局部头插。

代码语言：javascript复制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; inext; // 将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 个元素开始的，以此类推，反转区间的起点往后就是一个子问题，我们可以使用递归处理：

代码语言：javascript复制终止条件：当m == 1，就可以直接反转前n个元素。返回值：将已经反转后的子问题头节点返回给上一级。本级任务：递归地缩短区间，拼接本级节点与子问题已经反转的部分。

从头开始往后去掉前面不反转的部分

代码语言：javascript复制ListNode node = reverseBetween(head.next, m - 1, n - 1)

而每次反转，如果 n == 1，相当于只颠倒第一个节点，如果不是，则进入后续节点（子问题），因此反转过程也可以使用递归：

代码语言：javascript复制终止条件：当n == 1时，只反转当前头节点即可。返回值：将子问题反转后的节点头返回。本级任务：缩短 n 进入子问题反转，等子问题回到本级再反转当前节点与后续节点的连接。

颠倒后续的节点，直到n=1为最后一个

代码语言：javascript复制ListNode node = reverse(head.next, n - 1)

具体做法：

准备全局变量temp，最初等于null，找到递归到第n个节点时，指向其后一个位置，要将反转部分的起点（即反转后的尾）连接到这个指针。按照第一个递归的思路缩短子问题找到反转区间的起点，将反转后的部分拼接到前面正常的后面。按照第二个递归的思路缩短终点的子问题，从第n个位置开始反转，反转过程中每个子问题作为反转后的尾，都要指向temp。代码语言：javascript复制 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♪(･ω･)ﾉ谢谢阅读！！！下一篇文章见！！！

【本文地址】

【刷题】牛客

【刷题】牛客

今日新闻

推荐新闻