[LeetCode] 025. Reverse Nodes in k-Group (Hard) (C++/Java)

发布时间：2020-12-13 20:15:48 所属栏目：PHP教程来源：网络整理

导读：索引：[LeetCode] Leetcode 题解索引 (C/Java/Python/Sql) Github: https://github.com/illuz/leetcode 025. Reverse Nodes in k-Group (Hard) 链接：题目：https://oj.leetcode.com/problems/reverse-nodes-in-k-group/ 代码(github)：https://github.com

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github: https://github.com/illuz/leetcode

025. Reverse Nodes in k-Group (Hard)

链接：

题目：https://oj.leetcode.com/problems/reverse-nodes-in-k-group/
代码(github)：https://github.com/illuz/leetcode

题意：

把1个链表每 k 个分为1组，每组内进行翻转。
只能用常数级的空间。

分析：

这题比较考验链表的操作，用递归做会比较方便，先找到下1组的节点，把本组反转后再递归处理后面的节点。

代码：

C++:

class Solution { public: ListNode *reverseKGroup(ListNode *head,int k) { if (!head || !(head->next) || k < 2) return head; // count k nodes ListNode *nextgp = head; for (int i = 0; i < k; i++) if (nextgp) nextgp = nextgp->next; else return head; // reverse ListNode *prev = NULL,*cur = head,*next = NULL; while (cur != nextgp) { next = cur->next; if (prev) cur->next = prev; else cur->next = reverseKGroup(nextgp,k); prev = cur; cur = next; } return prev; } };

Java:

public class Solution { public ListNode reverseKGroup(ListNode head,int k) { ListNode cur = head; int cnt = 0; // get next group while (cur != null && cnt != k) { cur = cur.next; cnt++; } if (cnt == k) { cur = reverseKGroup(cur,k); // reverse while (0 <= --cnt) { ListNode tmp = head.next; head.next = cur; cur = head; head = tmp; } head = cur; } return head; } }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!