|4|[Median of Two Sorted Arrays][004]|Array, Binary Search, Divide and Conquer|

|10|[Regular Expression Matching][010]|String, Dynamic Programmin, Backtracking|

|23|[Merge k Sorted Lists][023]|Linked List, Divide and Conquer, Heap|

|25|[Reverse Nodes in k-Group][025]|Linked List|

[004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md

[010]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/010/README.md

[023]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/023/README.md

[025]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/025/README.md

Given a linked list, reverse the nodes of a linked list*k* at a time and return its modified list.

*k* is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of*k* then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,

Given this linked list:`1->2->3->4->5`

For*k* = 2, you should return:`2->1->4->3->5`

For*k* = 3, you should return:`3->2->1->4->5`

**Tags:** Linked List

题意是让你以`k`个元素为一组来翻转链表，最后不足`k`个的话不需要翻转，最传统的思路就是每遇到`k`个元素，对其`k`个元素进行翻转，而难点就是在此，下面介绍其原理，我们以例子中的`k = 3`为例，其`pre`和`next`如下所示。

我们要做的就是把`pre`和`next`之间的元素逆序，思想是依次从第二个元素到第`k`个元素，依次把它插入到`pre`后面，过程如下。

好了，根据原理，那写出代码就不难了。

classSolution {

publicListNodereverseKGroup(ListNodehead,intk) {

if (head==null|| k==1)return head;

ListNode node=newListNode(0), pre= node;

node.next= head;

for (int i=1; head!=null;++i) {

if (i% k==0) {

pre= reverse(pre, head.next);

head= pre.next;

}else {

head= head.next;

}

}

return node.next;

}

privateListNodereverse(ListNodepre,ListNodenext) {

ListNode head= pre.next;

ListNode move= head.next;

while (move!= next) {

head.next= move.next;

move.next= pre.next;

pre.next= move;

move= head.next;

}

return head;

}

}

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]

[title]:https://leetcode.com/problems/merge-k-sorted-lists

[ajl]:https://github.com/Blankj/awesome-java-leetcode

packagecom.blankj.hard._025;

importcom.blankj.structure.ListNode;

publicclassSolution {

publicListNodereverseKGroup(ListNodehead,intk) {

if (head ==null ||k ==1)returnhead;

ListNodenode =newListNode(0),pre =node;

node.next =head;

for (inti =1;head !=null; ++i) {

if (i %k ==0) {

pre =reverse(pre,head.next);

head =pre.next;

}else {

head =head.next;

}

}

returnnode.next;

}

privateListNodereverse(ListNodepre,ListNodenext) {

ListNodehead =pre.next;

ListNodemove =head.next;

while (move !=next) {

head.next =move.next;

move.next =pre.next;

pre.next =move;

move =head.next;

}

returnhead;

}

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

ListNode.print(solution.reverseKGroup(ListNode.createTestData("[1,2,3,4,5,6,7,8]"),3));

}

}