首页 > 代码库 > Reverse Nodes in k-Group[leetcode]递归和非递归的解法
Reverse Nodes in k-Group[leetcode]递归和非递归的解法
题目不难,但是容易出错,需要考虑各种边界情况
非递归代码如下:
ListNode *reverseKGroup(ListNode *head, int k) { if (head == NULL || k <= 1) return head; ListNode * start = NULL, * end = NULL, *newHead = NULL, *preEnd = NULL; while (true) { preEnd = end; if (!check(head, k)) { if (preEnd) preEnd->next = head; if (!newHead) newHead = head; return newHead; } reverse(head, k, &start, &end, &head); if (!newHead) newHead = start; if (preEnd) preEnd->next = start; } end->next = NULL; return newHead; } bool check(ListNode* head, int k) { for (int i = 1; i <= k; i++, head = head->next) { if (head == NULL) { return false; } } return true; } void reverse(ListNode *head, int k, ListNode** newHead, ListNode ** newTail, ListNode ** nextHead) { ListNode * pre, * next = head->next, * cur = head; * newTail = cur; for (int i = 2; i <= k; i++) { pre = cur; cur = next; next = cur->next; cur->next = pre; } * newHead = cur; * nextHead = next; }
如果用递归写会简单些:
ListNode *reverseKGroup(ListNode *head, int k) { if (k <= 1 || !check(head, k)) return head; ListNode* start, *end; reverse(head, k, &start, &end, &head); end->next = reverseKGroup(head, k); return start; } bool check(ListNode* head, int k) { for (int i = 1; i <= k; i++, head = head->next) if (head == NULL) return false; return true; } void reverse(ListNode *head, int k, ListNode** newHead, ListNode ** newTail, ListNode ** nextHead) { ListNode * pre, * next = head->next, * cur = head; * newTail = cur; for (int i = 2; i <= k; i++) { pre = cur; cur = next; next = cur->next; cur->next = pre; } * newHead = cur; * nextHead = next; }
Reverse Nodes in k-Group[leetcode]递归和非递归的解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。