给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。
链表元素个数不是k的倍数，最后剩余的不用翻转。
样例
给出链表 1->2->3->4->5
k = 2, 返回 2->1->4->3->5
k = 3, 返回 3->2->1->4->5
技巧
用dummy结点的原因是第一个结点在翻转时，指向第一个结点的指针要发生变化，新建一个dummy结点可以将所有的指针变化全部封装在函数里，无需而外修改指向容易操作
代码
- version1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/*
* @param head: a ListNode
* @param k: An integer
* @return: a ListNode
*/
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode curt = dummy;
// curt返回null时说明剩余结点数目不足k个
while (curt != null) {
// k + 1个结点（包括新建的头结点）的.next需要变化
curt = reverseNextK(curt, k);
}
// dummy虽然参与翻转，但变的是结点指向，
// 虽然链表的头结点会改变，但dummy.next永远指向链表的入口
return dummy.next;
}
private ListNode reverseNextK(ListNode node, int k) {
// node -> n1 -> n2 ... nk -> nk+1 ...
// ==>
// node -> nk -> nk-1...n1 -> nk+1...
// return n1
// n1要特别标记下来，因为最后要返回n1来得到下一组k个结点的头结点，
// 当反转后node.next就不是n1了
ListNode n1 = node.next;
// 给nk设置初值，nk不断遍历下一个结点，不足k个结点时，return null
ListNode nk = node;
for (int i = 0; i < k; i++) {
// 此处 nk 的后移和 if 判断语句的顺序不能颠倒，不然会出现空指针异常
// 原因是 nk 的初始定义是 node1 的前一个结点
nk = nk.next;
if (nk == null) {
return null;
}
}
// 翻转链表的模板
// 每k个结点reverse, nk在上面循环结束时指向了第k个结点
// 在翻转 k 个链表前要通过 for 循环找到第 k 个结点
ListNode nkplus = nk.next;
ListNode prev = null;
ListNode curt = n1;
// null -> n1 -> n2 ... nk -> nkplus
// ==>
// null <- n1 <- n2 ... nk <- nkplus
while (curt != nkplus) {
ListNode temp = curt.next;
curt.next = prev;
prev = curt;
curt = temp;
}
// connect，中间需要reverse的完成后需要把两端的指针连接好
// node代表头结点
// null -> nk —> nk - 1 ->...n1 -> nkplus
node.next = nk;
// n1和nk进行了位置交换
n1.next = nkplus;
return n1;
}
}
- version2
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
/**
* @param head a ListNode
* @param k an integer
* @return a ListNode
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null) {
head = reverseNextK(head, k);
}
return dummy.next;
}
// reverse head->n1->..->nk->next..
// to head->nk->..->n1->next..
// return n1
private ListNode reverseNextK(ListNode head, int k) {
// check there is enought nodes to reverse
ListNode next = head; // next is not null
for (int i = 0; i < k; i++) {
if (next.next == null) {
return next;
}
next = next.next;
}
// reverse
ListNode n1 = head.next;
ListNode prev = head, curt = n1;
for (int i = 0; i < k; i++) {
ListNode temp = curt.next;
curt.next = prev;
prev = curt;
curt = temp;
}
n1.next = curt;
head.next = prev;
return n1;
}
}