Top题解 | BM3#链表中的节点每k个一组翻转#
链表中的节点每k个一组翻转
https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e
代码:
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @author Senky * @date 2023.03.23 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1 */ /** * @brief reverse a list * @param pHead ListNode类 * @return ListNode类 */ struct ListNode* ReverseList(struct ListNode* pHead ) { 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; } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @param head ListNode类 * @param k int整型 * @return ListNode类 */ struct ListNode* reverseKGroup(struct ListNode* head, int k ) { // write code here struct ListNode* reversehead = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* reversetail = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* reversehead_front = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* reversetail_next = (struct ListNode*)malloc(sizeof(struct ListNode)); reversehead = head; reversehead_front = NULL; reversetail = head; /*reversetail_next始终指向reversetail的下一个结点*/ reversetail_next = reversetail->next; /*初次翻转标记*/ int firstreverse = 1; /*当前链表的尾结点的下一个不为空说明还要继续翻转*/ while(reversetail != NULL) { /*找到反转链表的尾结点*/ for(int reversenum = 1; reversenum < k; reversenum++) { if(reversetail->next != NULL) { reversetail = reversetail->next; } else { return head; } } if(reversetail->next != NULL) { reversetail_next = reversetail->next; } else { reversetail_next = NULL; } if(reversetail != NULL) { reversetail->next = NULL; if(1 == firstreverse) { /*初次翻转需要改变head指向*/ head = ReverseList(reversehead); firstreverse = 0; } else { /*链接翻转链表头部*/ reversehead_front->next = ReverseList(reversehead); } reversehead_front = reversehead;//下一个循环的reversehead_front指向本次循环的reversehead reversehead->next = reversetail_next;//链接翻转链表尾部 /*指针指向下一个翻转链表的头结点*/ reversehead = reversetail_next; reversetail = reversetail_next; } } return head; }
图解:
注:malloc的指针记得free掉
#TOP101#TOP101-BM系列 文章被收录于专栏
系列的题解