一、知识点:

链表、链表反转

二、文字分析:

  1. 创建一个虚拟头节点dummy,将其指向原链表的头节点head
  2. 计算链表的长度length,以便确定需要进行翻转的组数。
  3. 初始化两个指针prevcurr,分别指向当前组的前一个节点和当前组的第一个节点。
  4. 在每一组内,使用反转操作将节点的指针方向翻转。
  5. 连接相邻的组。
  6. 返回虚拟头节点的next指针。

计算链表的长度,所以时间复杂度为O(n),其中n是链表的长度。接下来,每次翻转k个节点需要进行k-1次节点交换,因此每个节点只会被访问一次,总的时间复杂度为O(n)。由于只使用了常数级别的额外空间,所以空间复杂度为O(1)。

三、编程语言:

java

四、正确代码:

import java.util.*;

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

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }

        for (int i = 0; i < length / k; i++) {
            for (int j = 1; j < k; j++) {
                ListNode next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = curr.next;
        }

        return dummy.next;
    }
}