Top101题解 | BM2#链表内指定区间反转#
链表内指定区间反转
https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c
Solution1:
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @brief 交换单链表数据域的值变相实现区间翻转,头指针后移,尾指针前移 * 但是单链表指针不能前移,时间复杂度O(n²),空间复杂度O(1) * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) { // write code here struct ListNode* front = head; struct ListNode* tail = head; for (int i = 1; i < m; i++) { front = front->next; } do { /* *每次将tail指向head,再通过循环最后指向第n个结点, *n每do循环一次减一,变相实现tail指针向前移动 */ tail = head; for(int j = 1; j < n; j++) { tail = tail->next; } int temp = front->val; front->val = tail->val; tail->val = temp; front = front->next; n--; } while ((front < tail) && (front!=NULL) && (tail!=NULL)); return head; }
Solution2:
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * @author Senky * @date 2023.03.17 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1 * @param pHead ListNode类 * @return ListNode类 */ #include <stdio.h> struct ListNode* ReverseList(struct ListNode* pHead ) { // write code here struct ListNode* prev = NULL; struct ListNode* curr = pHead; struct ListNode* next; //退出循环后curr指向NULL while(curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @brief * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ struct ListNode* reverseBetween(struct ListNode* head, int m, int n ) { // write code here if(m != n)//m、n不等于才需要翻转链表 { struct ListNode* front = head; struct ListNode* front_pre = NULL;//初始化默认m无前驱 /*m有前驱结点*/ if(1 != m) { front_pre = head; front = front->next; /*将front定位在第m个结点处*/ for (int i = 2; i < m; i++) { front = front->next; front_pre = front_pre->next; } } /*将tail定位在第n个结点处 *此时的n必定大于2 */ struct ListNode* tail = head; struct ListNode* tail_next = NULL;//初始化默认n无后继 /*将tail定位在第n个结点处*/ for (int j = 1; j < n; j++) { tail = tail->next; } if(tail->next != NULL) { tail_next = tail->next;//有后继 } /*将tail和tail_next断开,那么区间链表只有front到tail *同时front_pre和tail_next记录了区间链表的前驱和后继(如果有) */ tail->next = NULL; /* * 链表头:head * 区间表头:tail * 区间表尾:front *(1)front有前驱: *则head是链表头,区间翻转后需要用front_pre指向区间链表头结点 * (1')tail有后继 * 区间翻转后需要用区间表尾front指向tail_next * (1'')tail无后继 * 区间翻转后需要用区间表尾front指向tail_next(无后继tail_next为空) *(2)front无前驱: *则区间链表头tail是整个链表头,将head指向区间链表头结点 * (2')tail有后继 * 区间翻转后需要用区间表尾front指向tail_next * (2'')tail无后继 * 区间翻转后需要用区间表尾front指向tail_next(无后继tail_next为空) */ if(front_pre != NULL) { front_pre->next = ReverseList(front);//(1)front有前驱 } else { head = ReverseList(front);//(2)front无前驱 } front->next = tail_next; } return head; }
Solution2图解:
TOP101-BM系列 文章被收录于专栏
系列的题解