25. Reverse Nodes in k-Group

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

一刷
题解：先来看递归。思路很简单，先找到第 k 和 k + 1节点，对k + 1节点进行递归，之后再用reverse list的方法对前k个节点进行reverse即可

Time Complexity - O(n)， Space Complexity - O(n)
这种k个一组的LinkedList很适合用递归来做

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null || k<=1) return head;
        ListNode kthNode = head;
        int count = 1;
        while(count<k){
            if(kthNode == null) return head;
            kthNode = kthNode.next;
            count++;
        }
        
        if(kthNode == null) return head;
        ListNode kplusoneNode = kthNode.next;
        kthNode.next = null;
        ListNode newHead = reverse(head);
        head.next = reverseKGroup(kplusoneNode, k);
        return newHead;
    }
    
    private ListNode reverse(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        
        while(head!=null){
            ListNode tmp = head.next;
            head.next = dummy;
            dummy = head;
            head = tmp;
        }
        
        return dummy;
    }
}

二刷：
利用recursion 做更简洁，并且不用担心返回的head的问题。

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode curr = head;
    int count = 0;
    while (curr != null && count != k) { // find the k+1 node
        curr = curr.next;
        count++;
    }
    if (count == k) { // if k+1 node is found
        curr = reverseKGroup(curr, k); // reverse list with k+1 node as head
        // head - head-pointer to direct part, 
        // curr - head-pointer to reversed part;
        while (count-- > 0) { // reverse current k-group: 
            ListNode tmp = head.next; // tmp - next head in direct part
            head.next = curr; // preappending "direct" head to the reversed list 
            curr = head; // move head of reversed part to a new node
            head = tmp; // move "direct" head to the next node in direct part
        }
        head = curr;
    }
    return head;
}