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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        int n = 0;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode one = dummy;
		// 先遍历链表获取长度
        while (one.next != null) {
            n++;
            one = one.next;
        }
	  	// 获取k的整数倍
        int m = n / k;

        ListNode pre = dummy;
        for (int i = 0; i < m; i++) {	// n/k 组，依次反转
            ListNode cur = pre.next;
		  	ListNode nextTemp;			// 记录下一节点
            for (int j = 0; j < k - 1; j++) {
                nextTemp = cur.next;
                cur.next = nextTemp.next;
                nextTemp.next = pre.next;
                pre.next = nextTemp;
            }
            pre = cur;		// 更新前驱节点
        }

        return dummy.next;
    }
}

空间复杂度O(1)

时间复杂度：n + (n/k) * (k - 1) = 2n - n/k = n(2-1/k)，故时间复杂度为 n的规模，即O(n)