Nodes in the linked list are flipped in groups of k

描述

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身.

数据范围： \ 0 \le n \le 2000 0≤n≤2000 , 1 \le k \le 20001≤k≤2000 ,链表中每个元素都满足 0 \le val \le 10000≤val≤1000
要求空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)

例如：

给定的链表是 1\to2\to3\to4\to51→2→3→4→5

对于 k = 2k=2 , 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5

对于 k = 3k=3 , 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5

This topic has beenAC

 解题思路:

        拿到这题,One idea is to use the stack to write.As for why I thought of using a stack？Because it needs to be reversed,Here I see the requirements of the title,空间复杂度为 O(1).The first idea is to save the value,通过 newA new node has been implemented.但是仔细一想,It seems impossible,Because the space complexity is definitely not in line with this,突然灵机一动,We can use the stack to store nodes that are pointers,nice.

        1→2→3→4→5   k = 2时 

        1→2→3→4→5   k = 3时   

        4和5It doesn't need to be flipped,So if you use a stack, it will bring another problem,Because the stack structure is first in last out,If you use the stack to save it will definitely lead to,4,5will also be flipped.

        这里有两个解决方法,

        1.把4,5再次入栈(入另一个栈),然后再输出 ok

        2.Might as well not use the stack structure,We use a two-way queue(Moreover, the efficiency of inserting and deleting at the front and rear ends of the two-way queue is also quite high,So we use this structure best)

        Let's look at an example：

        1→2→3→4→5   k = 3时   

        准备工作,A pointer to this linked list head.一个deque,一个中间变量 tmpk

        Some handy auxiliary pointers s和ans

 Here we make a loop,while(head != nullptr)     是的,It can be done in one pass

 此时退出循环,okk

判断 que是否为空或者tmpk是否等于 0

如果que不为空的话,说明queAt this time, the node does not need to be flipped

所以

 那么这题就ok了,Of course the topic has some details,This can only be modified according to the actual test emptying

比如  {},2     {1,2},3    {1},2等

Attached the code I passed:

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        deque<ListNode*> sta;
        int tmpk = k;
        ListNode *s = nullptr;
        ListNode *ans = nullptr;
        while(head != nullptr)
        {
            sta.push_back(head);
            head = head->next;
            tmpk--;
            if(tmpk == 0)
            {
                if(s == nullptr)
                {
                    s = sta.back();
                    sta.pop_back();
                    ans = s;
                }
                
                while(!sta.empty())
                {
                    s->next = sta.back();
                    sta.pop_back();
                    s = s->next;
                }
               
                
                tmpk = k;
            }
           
           
        }
        

        
        while(!sta.empty())
        {
            if(s == nullptr)
            {
                    
                    s = sta.front();
              
                    sta.pop_front();
                    ans = s;
              
            }
            else
            {
                    
                    s->next = sta.front();
               
                    sta.pop_front();
                s= s->next;
              
            }
          
        }
        
        if(s != nullptr)
        s->next = nullptr;

        
        return ans;
    }
};