[Leetcode] Reverse Nodes in k-Group

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode reverseKGroup(ListNode head, int k) {
11         if(k <= 0) {
12             throw new IllegalArgumentException("k <= 0");
13         }
14         if(k == 1) {
15             return head;
16         }
17         
18         ListNode dummy1 = new ListNode(0);                 // head node of the original list
19         ListNode dummy2 = new ListNode(0), tail2 = null;   // head node of the working list for reversing
20         ListNode dummy3 = new ListNode(0), tail3 = dummy3; // head node of resulting list
21         dummy1.next = head;
22         dummy2.next = null;
23         dummy3.next = null;
24         
25         int i = 1; // the nth node in the original list
26         while(dummy1.next != null) {
27             // Remove from the original list
28             ListNode curr = dummy1.next;
29             dummy1.next = curr.next;
30             
31             // Add to the head of reversed list
32             curr.next = dummy2.next;
33             dummy2.next = curr;
34             
35             if(i % k == 0) { // a group of k nodes has been reversed
36                 tail3.next = dummy2.next;
37                 dummy2.next = null;
38                 tail3 = tail2;
39             }else if(i % k == 1) {
40                 tail2 = curr;
41                 tail2.next = null;
42             }
43             i++;
44         }
45         
46         while(dummy2.next != null) {
47             ListNode p = dummy2.next;
48             dummy2.next = p.next;
49             p.next = tail3.next;
50             tail3.next = p;
51         }
52         
53         return dummy3.next;
54     }
55 }