feat: add 025

Blankj · Blankj · commit 50a8e7666519 · 2017-10-16T15:11:55.000+08:00
diff --git a/README.md b/README.md
@@ -73,6 +73,7 @@
 |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|
 
 
 
@@ -126,3 +127,4 @@
 [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
diff --git a/note/025/README.md b/note/025/README.md
@@ -0,0 +1,101 @@
+# [Merge k Sorted Lists][title]
+
+## Description
+
+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`如下所示。
+```
+0->1->2->3->4->5
+|           |
+pre        next
+```
+我们要做的就是把`pre`和`next`之间的元素逆序，思想是依次从第二个元素到第`k`个元素，依次把它插入到`pre`后面，过程如下。
+```
+ head move
+   |  |
+0->1->2->3->4->5
+|           |
+pre        next
+
+    head move
+      |  |
+0->2->1->3->4->5
+|           |
+pre        next
+
+       head move
+         |  |
+0->3->2->1->4->5
+|           |
+pre        next
+```
+好了，根据原理，那写出代码就不难了。
+
+
+```java
+/**
+ * Definition for singly-linked list.
+ * public class ListNode {
+ *     int val;
+ *     ListNode next;
+ *     ListNode(int x) { val = x; }
+ * }
+ */
+class Solution {
+    public ListNode reverseKGroup(ListNode head, int k) {
+        if (head == null || k == 1) return head;
+        ListNode node = new ListNode(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;
+    }
+
+    private ListNode reverse(ListNode pre, ListNode next) {
+        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
diff --git a/src/com/blankj/hard/_025/Solution.java b/src/com/blankj/hard/_025/Solution.java
@@ -0,0 +1,45 @@
+package com.blankj.hard._025;
+
+import com.blankj.structure.ListNode;
+
+/**
+ * <pre>
+ *     author: Blankj
+ *     blog  : http://blankj.com
+ *     time  : 2017/10/16
+ *     desc  :
+ * </pre>
+ */
+public class Solution {
+    public ListNode reverseKGroup(ListNode head, int k) {
+        if (head == null || k == 1) return head;
+        ListNode node = new ListNode(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;
+    }
+
+    private ListNode reverse(ListNode pre, ListNode next) {
+        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;
+    }
+
+    public static void main(String[] args) {
+        Solution solution = new Solution();
+        ListNode.print(solution.reverseKGroup(ListNode.createTestData("[1,2,3,4,5,6,7,8]"), 3));
+    }
+}
