链表中的节点每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

---

本题已AC

---

 解题思路:

        拿到这题，一个想法就是用栈来写。至于为什么我会想到用栈呢？因为需要反向嘛，这里我看题目的要求，空间复杂度为 O(1)。第一个想法是保存值，通过 new一个新的节点了实现。但是仔细一想，好像不可以的，因为这样空间复杂度肯定不符合，突然灵机一动，我们可以用栈保存节点是指针，nice.

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

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

        4和5是不用翻转的，所以如果用栈又会带来一个问题，因为栈结构是先进后出的，如果用栈来保存肯定会导致，4，5也会被翻转。

        这里有两个解决方法，

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

        2.不妨我们不使用栈结构，我们使用双向队列(而且双向队列在前后两端进行插入删除的效率也挺高的，所以我们使用这个结构最佳了)

        我们哪一个例子来看：

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

        准备工作，一个指向该链表的指针 head。一个deque,一个中间变量 tmpk

        一些方便操作的辅助指针 s和ans

       

 

 

 

 

 这里我们做一个循环，while(head != nullptr)     是的，一次遍历就可以搞定

 

 此时退出循环，okk

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

如果que不为空的话，说明que此时的节点是不需要翻转的

所以

 那么这题就ok了,当然题目有一些细节，这个只能根据实际的测试清空来修改了

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

附上我通过的代码:

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