题解 | #链表中的节点每k个一组翻转#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if (k == 1) return head;
        if (head == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode foreNode = dummy;
        ListNode leftNode = foreNode.next;
        ListNode rightNode = leftNode;
        ListNode backNode = leftNode;
        //初始化固定节点
        for (int i = 1; i < k; i++) {
            rightNode = rightNode.next;
            if (rightNode == null) return head;
        }
        
        while (leftNode != null && rightNode != null) {
            backNode = rightNode.next;
            //断开节点
            foreNode.next = null;
            rightNode.next = null;

            //反转中间left-right节点
            reverseListNode(leftNode);

            //重新连接节点
            foreNode.next = rightNode;
            leftNode.next = backNode;

            //重新固定节点
            foreNode = leftNode;
            leftNode = backNode;
            if (leftNode == null) break;
            rightNode = leftNode;
            for (int i = 1; i < k; i++) {
                rightNode = rightNode.next;
                if (rightNode == null) break;
            }
        }
        return dummy.next;
    }

    private ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
}

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        if (k == 1) return head;
        if (head == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode foreNode = dummy;
        ListNode leftNode = foreNode.next;
        ListNode rightNode = leftNode;
        ListNode backNode = leftNode;
        //初始化固定节点
        for (int i = 1; i < k; i++) {
            rightNode = rightNode.next;
            if (rightNode == null) return head;
        }
        
        while (leftNode != null && rightNode != null) {
            backNode = rightNode.next;
            //断开节点
            foreNode.next = null;
            rightNode.next = null;

            //反转中间left-right节点
            // reverseListNode(leftNode);
            Deque<ListNode> deque = new LinkedList<>();
            ListNode tempNode = leftNode;
            for (int i=0; i<k; i++) {
                deque.addLast(tempNode);
                tempNode = tempNode.next;
            }
            ListNode reNode = deque.removeLast();
            while (!deque.isEmpty()) {
                reNode.next = deque.removeLast();
                reNode = reNode.next;
            }
            reNode.next = null;

            //重新连接节点
            foreNode.next = rightNode;
            leftNode.next = backNode;

            //重新固定节点
            foreNode = leftNode;
            leftNode = backNode;
            if (leftNode == null) break;
            rightNode = leftNode;
            for (int i = 1; i < k; i++) {
                rightNode = rightNode.next;
                if (rightNode == null) break;
            }
        }
        return dummy.next;
    }

    private ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;
        }
        return pre;
    }
}