一、知识点:
链表、链表反转
二、文字分析:
- 创建一个虚拟头节点
dummy,将其指向原链表的头节点head。 - 计算链表的长度
length,以便确定需要进行翻转的组数。 - 初始化两个指针
prev和curr,分别指向当前组的前一个节点和当前组的第一个节点。 - 在每一组内,使用反转操作将节点的指针方向翻转。
- 连接相邻的组。
- 返回虚拟头节点的
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;
}
}

京公网安备 11010502036488号