LeetCode开心刷题十四天——25Reverse Nodes in k-Group

叁歲伎倆 2023-08-17 15:14 95阅读 0赞

25. Reverse Nodes in k-Group

Hard

1222257FavoriteShare

Given a linked list, reverse the nodes of a linked list *k* at a time and return its modified list.

*k* is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of *k* then left-out nodes in the end should remain as it is.

Example:

Given this linked list: `1->2->3->4->5`

For *k* = 2, you should return: `2->1->4->3->5`

For *k* = 3, you should return: `3->2->1->4->5`

Note:

*  Only constant extra memory is allowed.
 *  You may not alter the values in the list's nodes, only nodes itself may be changed

改进声明：

本方法速度和内存好像都比较差，虽然思路简洁，但是可能构造技巧上还是有进步空间

![1005283-20190707103635694-588232289.png][]

main idea:

One word to sum up the idea,victory! haaa~just a joke

Group

In this reverse problem,group is important,devide into ordered &inordered.three pointers we need to correctly understanding the meaning of these variables.cur->ordered part end ,nxt->inordered start,pre->before these parts.

It looks like this composition:

pre->order part->inorder part->left\_out

Now it's the code

#include <iostream>
    #include<vector>
    #include<iostream>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    #include<iomanip>
    #include<vector>
    #include<list>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<map>
    using namespace std;
    struct ListNode {
          int val;
          ListNode *next;
          ListNode(int x) : val(x), next(NULL) {}
      };
    
    class Solution {
    public:
        ListNode* reverseKGroup(ListNode* head, int k) {
            //this situation can include head->next
            //special case dispose
            if(!head||k==1) return head;
    
            //dummy node
            ListNode dummy(0);
            dummy.next=head;
            //len calc
            int len=1;
            while(head=head->next) len++;
    
            //cout<<len<<endl;
    
            ListNode *pre=&dummy;
            for(int i=0;i+k<=len;i+=k)
            {
                ListNode *cur=pre->next;
                ListNode *nxt=cur->next;
                for(int j=1;j<k;j++)
                {
                    cur->next=nxt->next;
                    nxt->next=pre->next;
                    pre->next=nxt;
                    nxt=cur->next;
                }
                pre=cur;
            }
            return dummy.next;
    
        }
    };
    int main()
    {
        int k;
        cin>>k;
        ListNode a(1);
        ListNode b(2);
        ListNode c(3);
        ListNode d(4);
        ListNode e(5);
        Solution s;
        a.next=&b;
        b.next=&c;
        c.next=&d;
        d.next=&e;
        ListNode *head=&a;
    //    while(head)
    //    {
    //        cout<<head->val<<endl;
    //        head=head->next;
    //    }
        ListNode* res=NULL;
        res=s.reverseKGroup(head, k);
        while(res)
        {
            cout<<res->val<<endl;
            res=res->next;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Marigolci/p/11145448.html

[1005283-20190707103635694-588232289.png]: /images/20230810/c11bdbda022244069155e4cbc1a4ffb3.png