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

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

阅读量：4557 次

发布时间：2019-06-08

本文共 2176 字，大约阅读时间需要 7 分钟。

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

改进声明：

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

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 
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  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<
                   
                    <
                    
                     next; ListNode *nxt=cur->next; for(int j=1;j
                     
                      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<
                      
                       val<
                       
                        next;// } ListNode* res=NULL; res=s.reverseKGroup(head, k); while(res) { cout<
                        
                         val<
                         
                          next; } return 0;}

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

你可能感兴趣的文章