一、知识点:
链表、链表反转
二、文字分析:
- 创建一个虚拟头节点
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; } }