题意:给定一个链表和数字k,要求每k个节点翻转,返回链表头。如果链表长度不是k的倍数,剩余部分不做处理。
25. Reverse Nodes in k-Group (opens new window)
此题是上一题的扩展,要求每k个节点做翻转,问题可以分三步解决,把链表拆分为n个部分,对其做链表翻转,最后将其拼接起来。因为需要知道链表长度才能判断是否有剩余部分,所以多遍历了一遍链表。时间复杂度为O(2n),空间复杂度为O(1)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int size = 0;
ListNode tmp = head;
// 计算链表长度
while (tmp != null) {
size++;
tmp = tmp.next;
}
// head前拼接一个节点,方便后续处理
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode left = null;
ListNode right = null;
// 计算需要翻转的部分
for (int i = 0; i <= size - k; i += k) {
left = prev.next;
// 返回翻转后的head
right = reverse(left, k);
// 上一段拼接上right
prev.next = right;
// 重置prev
prev = left;
}
return dummy.next;
}
private ListNode reverse(ListNode head, int k) {
// 翻转链表,把head.next指向tail.next,返回翻转后的head
ListNode last = null;
ListNode current = head;
ListNode next = null;
for (int i = 0; i < k; i++) {
next = current.next;
current.next = last;
last = current;
current = next;
}
head.next = next;
return last;
}
}