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

Fork= 2, you should return:2->1->4->3->5

Fork= 3, you should return:3->2->1->4->5

Analysis

split into 2 steps to solve

Solution from Forum

public ListNode reverseKGroup(ListNode head, int k) {
    //1. test weather we have more then k node left, if less then k node left we just return head 
    ListNode node = head;
    int count = 0;
    while (count < k) { 
        if(node == null)return head;
        node = node.next;
        count++;
    }
    // 2.reverse k node at current level 
       ListNode pre = reverseKGroup(node, k); //pre node point to the the answer of sub-problem 
        while (count > 0) {  
            ListNode next = head.next; 
            head.next = pre; 
            pre = head; 
            head = next;
            count = count - 1;
        }
        return pre;
}

Iterative Solution

public ListNode reverseKGroup(ListNode head, int k) {
    int l = 0;
    ListNode itr = head;
    while (itr != null) {
        itr = itr.next;
        l++;
    }
    if (l < k) {
        return head;
    }
    int n = l / k;
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    ListNode pre = null;
    ListNode tail = null;
    for (int i = 0; i < n; ++i) {
        tail = head;
        for (int j = 0; j < k; ++j) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        cur.next = pre;
        tail.next = head;
        pre = tail;
        cur = tail;
    }
    return dummy.next;
}