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

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

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

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

改进声明：

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

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;
}