题解 | #最长的括号子串#

链表中的节点每k个一组翻转
将给出的链表中的节点每k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
要求空间复杂度 O(1)

示例
输入：{1,2,3,4,5},2
返回值：{2,1,4,3,5}

方法一 模拟法

将一条链表分块分为链表长度/k块链表，如果处不尽则说明后面会有剩下的那一块是不满长度为k的。在最初的时候需要定义两个NodeList表示result(结果)和 now(当前所到达的结果链表的位置)。之后遍历块的长度，对每一个链表块进行翻转，再翻转完后将完成的链表插入到now链表的下一个，再将now链表更新到最前即可。

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(k <= 1) return head;
        if(head == null) return head;
        ListNode node = head;
        int len = length(head);
        head = node;
        int sx = len / k;    //分成sx块向下取整（默认向下） 因为处不尽的后面必然凑不满k个
        ListNode result = new ListNode(0);
        ListNode now = result;
        int cnt = 0;
        for(int i = 0; i < sx; i ++){
            ListNode tmp = null;
            for(int j = 0; j < k; j ++){    //将第i块的元素翻转
                ListNode bl = head.next;
                head.next = tmp;
                tmp = head;
                head = bl;
            } 
            now.next = tmp;
            while(now.next != null) now = now.next;    //将now更新到最前的一个点
        }
        now.next = head;
        return result.next;
    }
    public int length(ListNode now){    //获取链表长度
        int cnt = 0;
        if(now != null) cnt = 1;
        while(now.next != null){
            cnt ++; now = now.next;
        }
        return cnt;
    }
}

时间复杂度： O(n) 获取链表长度，翻转链表，和now变量的指位都需要遍历一次链表所以总时间复杂度为O(n).
空间复杂度： O(1) 只使用了若干个变量

方法二 栈

和方法一一样将链表分成每段长度为k的子链表，将每个链表存入栈中，当栈中有k个元素即可一一取出，之后按取出的顺序重组链表就是这一段中翻转的链表，要注意的是处理尾部不满长度为k的链表块时直接取栈底的元素做为最后一段即可。

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(k <= 1 || head == null) return head;
        Deque<ListNode> st = new ArrayDeque<ListNode>();    //模拟栈
        ListNode result = new ListNode(0);
        ListNode now = result;
        int cnt = 0;
        while(true){
            for(int i = 0; i < k; i ++){    //将当前链表前k个存入栈中
                st.push(head);
                head = head.next;
                cnt ++;
                if(head == null) break;
            }
            if(cnt == k){    //如果当前栈中有k个元素则一一取出存入链表
                while(!st.isEmpty()){
                    now.next = st.pop();
                    now = now.next; now.next = null;
                }
            }
            if(head == null) break;   //如果链表取完了跳出循环
            cnt = 0;
        }
        ListNode end = null;
        while(!st.isEmpty()){    //如果栈中还有剩下的就说明是最后的一块直接取栈底即可
            end = st.pop();
        }
        now.next = end;
        return result.next;
    }

时间复杂度 O(n) 遍历了整个链表并且重组链表使用了时间为2n
空间复杂度 O(k) 栈中存入最大有k个ListNode