1616public class ReverseKGroup {
1717// Solution 1:
1818// recursion.
19+ // 思路是先反转，如果发现长度不够K，再翻回来
1920public ListNode reverseKGroup1 (ListNode head ,int k ) {
2021if (head ==null ) {
2122return null ;
@@ -24,16 +25,6 @@ public ListNode reverseKGroup1(ListNode head, int k) {
2425return rec (head ,k );
2526 }
2627
27- public class ReturnType {
28- ListNode head ;
29- ListNode tail ;
30-
31- ReturnType (ListNode head ,ListNode tail ) {
32- this .head =head ;
33- this .tail =tail ;
34- }
35- }
36-
3728public ListNode rec (ListNode head ,int k ) {
3829ListNode dummy =new ListNode (0 );
3930
@@ -70,4 +61,66 @@ public ListNode rec(ListNode head, int k) {
7061
7162return dummy .next ;
7263 }
64+
65+ /*
66+ * Solution 2:
67+ * 使用区间反转的办法, iteration.
68+ * */
69+ public ListNode reverseKGroup (ListNode head ,int k ) {
70+ if (head ==null ) {
71+ return null ;
72+ }
73+
74+ ListNode dummy =new ListNode (0 );
75+ dummy .next =head ;
76+
77+ ListNode cur =head ;
78+ ListNode pre =dummy ;
79+
80+ int cnt =0 ;
81+
82+ while (cur !=null ) {
83+ cnt ++;
84+ if (cnt ==k ) {
85+ cnt =0 ;
86+ pre =reverse (pre ,cur .next );
87+ }
88+ cur =cur .next ;
89+ }
90+
91+ return dummy .next ;
92+ }
93+
94+ /**
95+ * Reverse a link list between pre and next exclusively
96+ * an example:
97+ * a linked list:
98+ * 0->1->2->3->4->5->6
99+ * | |
100+ * pre next
101+ * after call pre = reverse(pre, next)
102+ *
103+ * 0->3->2->1->4->5->6
104+ * | |
105+ * pre next
106+ * @param pre
107+ * @param next
108+ * @return the reversed list's last node, which is the precedence of parameter next
109+ */
110+ private static ListNode reverse (ListNode pre ,ListNode next ){
111+ ListNode cur =pre .next ;
112+
113+ // record the new tail.
114+ ListNode last =cur ;
115+ while (cur !=next ) {
116+ ListNode tmp =cur .next ;
117+ cur .next =pre .next ;
118+ pre .next =cur ;
119+ cur =tmp ;
120+ }
121+
122+ last .next =next ;
123+ return last ;
124+ }
125+
73126}