@@ -6,31 +6,80 @@ public class _25 {
66
77/**We use recursion to go all the way until the end: when the number of nodes are smaller than k;
88 * then we start to reverse each group of k nodes from the end towards the start.*/
9- public ListNode reverseKGroup (ListNode head ,int k ) {
10- ListNode curr =head ;
11- int count =0 ;
12- while (curr !=null &&count !=k ) {
13- //find the k+1 node
14- curr =curr .next ;
15- count ++;
9+ public static class Solution1 {
10+ public ListNode reverseKGroup (ListNode head ,int k ) {
11+ ListNode curr =head ;
12+ int count =0 ;
13+ while (curr !=null &&count !=k ) {
14+ //find the k+1 node
15+ curr =curr .next ;
16+ count ++;
17+ }
18+
19+ if (count ==k ) {
20+ /**after this below recursive call finishes, it'll return head;
21+ * then this returned "head" will become "curr", while the head
22+ * in its previous callstack is the real head after this call.
23+ * Setting up a break point will make all of this crystal clear.*/
24+ curr =reverseKGroup (curr ,k );
25+
26+ while (count -- >0 ) {
27+ ListNode temp =head .next ;
28+ head .next =curr ;
29+ curr =head ;
30+ head =temp ;
31+ }
32+ head =curr ;
33+ }
34+ return head ;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
1635 }
36+ }
37+
38+ public static class Solution2 {
39+ public ListNode reverseKGroup (ListNode head ,int k ) {
40+ if (head ==null ||head .next ==null ||k ==1 ) {
41+ return head ;
42+ }
43+
44+ int n =0 ;// number of nodes
45+
46+ ListNode curr =head ;
47+ while (curr !=null ){
48+ n ++;
49+ curr =curr .next ;
50+ }
51+
52+ ListNode prev =null ;
53+ ListNode next =null ;
54+ ListNode newHead =null ;
55+ ListNode tail1 =null ;
56+ ListNode tail2 =head ;
57+
58+ curr =head ;
1759
18- if (count ==k ) {
19- /**after this below recursive call finishes, it'll return head;
20- * then this returned "head" will become "curr", while the head
21- * in its previous callstack is the real head after this call.
22- * Setting up a break point will make all of this crystal clear.*/
23- curr =reverseKGroup (curr ,k );
24-
25- while (count -- >0 ) {
26- ListNode temp =head .next ;
27- head .next =curr ;
28- curr =head ;
29- head =temp ;
60+ while (n >=k ) {
61+ // reverse nodes in blocks of k
62+ for (int i =0 ;i <k ;i ++) {
63+ // linked List reversal code
64+ next =curr .next ;
65+ curr .next =prev ;
66+ prev =curr ;
67+ curr =next ;
68+ }
69+ if (newHead ==null ) {
70+ newHead =prev ;
71+ }
72+ if (tail1 !=null ) {
73+ tail1 .next =prev ;
74+ }
75+ tail2 .next =curr ;// when n is not multiple of k
76+ tail1 =tail2 ;
77+ tail2 =curr ;
78+ prev =null ;
79+ n -=k ;
3080 }
31- head = curr ;
81+ return newHead ;
3282 }
33- return head ;//we run out of nodes before we hit count == k, so we'll just directly return head in this case as well
3483 }
3584
3685}