描述

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

例如：给定的链表是 1->2->3->4->5

• 对于 k=2 , 你应该返回 2->1->4->3->5
• 对于 k=3 , 你应该返回 3->2->1->4->5

思路1：使用双端队列

将链表分段反转，空间复杂度O(n)

1. 遍历将元素加入"栈"中，并计数
2. 当数量达到k，将所有元素出栈，反转成新链表
3. 数量重置为0
4. 重复上面的步骤，直到链表为空
5. 此时如果数量小于k，则将栈底的元素取出，直接接到新链表上，不需要反转

双端队列既可以当栈用，也可以当队列用，因此可以从栈顶取出元素，也可以从栈底取出

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        Deque<ListNode> deque = new LinkedList<>();
        int count = 0;
        while(true) {
            if(head == null) {
                break;
            }
            //入栈
            deque.push(head);
            head = head.next;
            count++;
            if(count == k) {
                //反转链表：出栈
                while(!deque.isEmpty()) {
                    cur.next = deque.pop();
                    cur = cur.next;
                    //将下一个节点置空，防止形成环
                    cur.next = null;
                }
                //重新开始计数
                count = 0;
            }
        }
        //poll为空的话会返回null，因此不需要判空
        cur.next = deque.pollLast();
        return ret.next;
    }
}

思路2：使用三指针

整体过程和思路1类似，只是把链表反转改为了三指针，使用head和tail记录分段链表的开始和结尾。空间复杂度O(1)

这里的三指针反转有点不一样，例如：1->2->3->4->5，k=3

1. 需要先反转为3->2->1->null
2. 然后将新链表指向反转后的头节点，即cur->3->2->1
3. 再将cur移至新链表末尾

public class Solution {
    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode ret = new ListNode(0);
        ListNode cur = ret;
        ListNode tail = head;
        int count = 0;
        while(true) {
            if(tail == null) {
                break;
            }
            tail = tail.next;
            count++;
            if(count == k) {
                //反转链表
                ListNode pre = null;
                while(head != tail) {
                    ListNode next = head.next;
                    head.next = pre;
                    pre = head;
                    head = next;
                }
                //新链表指向反转后的头节点
                cur.next = pre;
                //新链表移到最后
                while(cur.next != null) {
                    cur = cur.next;
                }
                //重新开始计数
                count = 0;
            }
        }
        cur.next = head;
        return ret.next;
    }
}