本文主要是介绍leetcode25. Reverse Nodes in k-Group,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:题目链接
这题是hard诶,题目本身难度其实还好,但我debug是真的hard…
思路:把这题拆开,首先解决如何反转k个结点的链表?
首先创建一个头结点root,root->next=nullptr。然后依次插入结点。
然后我们再输出root->next,这样是不是就反转了链表呀。知道了逻辑,我们开始敲代码:
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* root = new ListNode();ListNode* dummy_node = root;while(head){ListNode* root_next_node = root->next;root->next = head;ListNode* head_next_node = head->next;head->next = root_next_node;head = head_next_node;}return dummy_node->next;}
};
参考例题:反转列表
好,解决了反转k个结点的列表的问题,我们只需要判断剩下的结点到底是否>k,否则不需要反转剩下的了。
那么,我们就要从反转中得到一些信息。什么信息?反转后列表的第一个结点。以及该列表的下一个结点,因为这个结点是我们下次反转(如果需要反转的话)的起点。
还有一点,我们对于整个列表而言还需要一个头结点,因为我们要反转很多次⌊n/k⌋。所以我们要每次都把反转好的链表加入到头结点后面,注意头结点每次都要是当前答案链表的最后一个元素哦。!!
其他的细节看代码就可以了:
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverse(ListNode* head, int k, ListNode*& next_node) {//反转从head开始的k个结点,并第k+1个结点赋值给next_node。注意最后一个是引用,因为要修改实际值哦ListNode* root = new ListNode();//头结点while (k--) {//执行k次,每次把head结点插入到root后面,这样就可以反转了ListNode* p = root->next;root->next = head;ListNode* q = head->next;head->next = p;head = q;next_node = q;}return root->next;}ListNode* reverseKGroup(ListNode* head, int k) {if (!(head && head->next)) return head;//如果没有或只有一个,直接返回就可以了ListNode* root = new ListNode();//用来当头结点,方便操作ListNode* begin = head;//每次将要反转链表的第一个结点ListNode* res = root;//用来保存root的头结点,因为最后是要输出第一个结点while (head){begin = head;for (int i = 1; i < k; ++i) {head = head->next;if (!head) {//如果没有k个,直接把后面的结点都接到root后面,然后返回就可以了root->next = begin;return res->next;}}//正常表示有k个root->next = reverse(begin, k, head);//执行反转操作,返回被反转链表的第一个结点root = begin;//将root指向答案链表的最后一个元素}return res->next;}};
大概就是这样了,其他的细节只要你动手实现,应该就可以看懂的。加油加油加油!!!
这篇关于leetcode25. Reverse Nodes in k-Group的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!