# 25 Reverse Nodes in k-Group

input是一個linked list和integer k， k表示linked list中每k個node要reverse一次。

例如 input : 1->2->3->4->5 output : 2->1->4->3->5

Concept: move head by k each time reverse 長度為k的子linked list，再跟前後接起來。

實作: -Main:

1. create a dummyhead to record the beginning of the input linked list. ListNode begin = dummyhead.
2. head當作讀取ListNode的pointer，int i=0 當作數跑了幾個node的counter
3. while(head!=null)，若還沒跑k圈，head就移動到下個node，若已經跑k圈了，呼叫reverse(begin, head.next)，要reverse的start node的前一個和end node的後一個。 -reverse():
4. current node: begin.next
5. previous node: begin
6. first node = current node -> k-group的第一個
7. next node每迴圈記錄下一個node
8. while(current node還沒到k-group的最後一個) 先記錄next = cur.next current node的下一個要接回previous node 接好之後，移動cur和prev pointer: prev = cur, cur = next
9. 從迴圈出來後，原本的begin要接到k-group的最後一個---也就是prev
10. first.next要存下一個k-group的第一個---也就是cur
11. 回傳first(此k-group的最後一個)

Pseudocode:

ListNode dummyhead
dummyhead.next = head
ListNode begin = dummyhead;
int i=0;
while head!=null
    i++
    if i%k==0
        begin = reverse(begin,head.next)
    else
        head = head.next
return dummyhead.next;

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {

        if(head==null || head.next==null || k==1)  return head;
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        ListNode begin = dummyhead;
        int i=0;
        while(head!=null){
            i++;
            if(i%k==0){
                begin = reverse(begin,head.next);
                head = begin.next;
            }
            else
                head = head.next;
        }
        return dummyhead.next;
    }
    ListNode reverse(ListNode begin, ListNode end){
        ListNode cur = begin.next;
        ListNode next, first;
        ListNode prev = begin;
        first = cur;
        while(cur!=end){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        begin.next = prev;
        first.next = cur;
        return first;
    }
}