LeetCode: 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.

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

---

Find if there are enough nodes to reverse first, then do the reverse. I implemented iterative way in C++, recursive way in Python.

C++ Code:

/*
 * func: reverse_k_nodes
 * goal: reverse k nodes in a linked list. If there are less than k,
 we don't reverse
 * @param head: head node of the linked list
 * @param k: the number of nodes k
 * return: the new head of the linked list
 */
/*
 * 1. Check availability to reverse
 * 2. Get the node next to the kth node,
 and make it as the first previous node
 * 3. Make the head node as current node
 * 4. Make the node next ot head node as the first next node
 * 4. Make current node's next point to previous
 * 5. Change current node to next node
 * 6. Make next node move forward by 1
 */
ListNode* reverse_k_nodes(ListNode* head, int k){
    if(k <= 1 || head == nullptr){
        return head;
    }
    //To check if there are at least k nodes in the current linked list
    int count = 1;
    ListNode* new_head = head;
    while(new_head->next != nullptr && count < k){
        ++count;
        new_head = new_head->next;
    }
    
    if(count < k){
        return head;
    }else{
        //Get node next to the current tail
        ListNode* previous = new_head->next;
        ListNode* current = head;
        ListNode* next = current->next;
        while(current != new_head){
            current->next = previous;
            previous = current;
            current = next;
            next = next->next;
        }
        current->next = previous;
        return new_head;
    }
}

/*
 * func: reverse_k_group
 * goal: reverse the nodes of a linked list k at a time
 * @param head: head node of the linked list
 * @param k: the group number k
 * return: the modified linked list
 */
/*
 * keep reverse k nodes from the head until the reversing fails
 */
ListNode* reverse_k_group(ListNode *head, int k){
    ListNode *old_head = head;
    ListNode *new_head = reverse_k_nodes(old_head, k);
    ListNode *ret = new_head;
    while(new_head != old_head){
        //Get the previous tail node ahead of next k-group
        ListNode *previous_tail = old_head;
        //Get the old head for the next iteration
        old_head = old_head->next;
        //Get the new head for this iteration
        new_head = reverse_k_nodes(old_head, k);
        //Linked the previous tail node and current new head
        previous_tail->next = new_head;
    }
    
    return ret;
}

Python Code:

# func: reverse the nodes of a linked list k at a time and return its modified list
# @param head: head node of the linked list
# @param k: the number of nodes in a group
# return: head node of the modified linked list
def reverse_k_group(head, k):
    if not head or k <= 1:
        return head
    else:
        count = 1
        new_head = head
        while new_head.next and count < k:
            count += 1
            new_head = new_head.next

        #There are not enough to reverse
        if count < k:
            return head
        else:
            #head for the next iteration
            next_head = new_head.next
            current_node = head
            previous_node = next_head
            next_node = head.next
            while next_node != next_head:
                #Make current node point to the previous one
                current_node.next = previous_node
                #Change the previous one to the current one
                previous_node = current_node
                #Change current one to the next one
                current_node = next_node
                #Move next node forward
                next_node = next_node.next
            #Link the last one to the previous one
            current_node.next = previous_node
            #Go to the next iteration
            head.next = reverse_k_group(next_head, k)

            return new_head