Reverse Nodes in k-Group

---

Reverse Nodes in k-Group: Given the head of a linked list, reverse the nodes of the list k at a time, and return the 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 list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

---

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

---

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

---

Try this Problem on your own or check similar problems:

1. Swap Nodes in Pairs
2. Swapping Nodes in a Linked List
3. Reverse Nodes in Even Length Groups

Solution:

Java

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1, head), iter = dummy.next, start = dummy;

    int listLength = 0;
    while(iter != null){
        ++listLength;
        iter = iter.next;
    }

    iter = dummy.next;

    int numberOfReverse = listLength / k;

    for(int i = 0; i < numberOfReverse; ++i){
        for(int j = 0; j < k - 1; ++j){
            ListNode next = iter.next;
            iter.next = next.next;
            next.next = start.next;
            start.next = next;
        }
        start = iter;
        iter = iter.next;
    }

    return dummy.next;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  const dummy = new ListNode(-1, head);
  let iter = dummy.next;
  let start = dummy;

  let listLength = 0;
  while (iter != null) {
    listLength++;
    iter = iter.next;
  }

  iter = dummy.next;

  let numberOfReverse = Math.floor(listLength / k);

  for (let i = 0; i < numberOfReverse; i++) {
    for (let j = 0; j < k - 1; j++) {
      let next = iter.next;
      iter.next = next.next;
      next.next = start.next;
      start.next = next;
    }
    start = iter;
    iter = iter.next;
  }

  return dummy.next;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(-1, head)
        iter = dummy.next
        start = dummy

        listLength = 0
        while iter != None:
            listLength += 1
            iter = iter.next

        iter = dummy.next

        numberOfReverse = listLength // k

        for i in range(numberOfReverse):
            for j in range(k - 1):
                next = iter.next
                iter.next = next.next
                next.next = start.next
                start.next = next
            start = iter
            iter = iter.next

        return dummy.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1, head);
        ListNode* iter = dummy->next;
        ListNode* start = dummy;

        int listLength = 0;
        while (iter != nullptr) {
            listLength++;
            iter = iter->next;
        }

        iter = dummy->next;

        int numberOfReverse = listLength / k;

        for (int i = 0; i < numberOfReverse; i++) {
            for (int j = 0; j < k - 1; j++) {
                ListNode* next = iter->next;
                iter->next = next->next;
                next->next = start->next;
                start->next = next;
            }
            start = iter;
            iter = iter->next;
        }

        return dummy->next;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

At most we will traverse through the whole linked list leading to a linear time complexity. We first calculate the length of linked list to see how many times we need to reverse, or in other words how many groups are there. We utilize the same algorithm we implemented in Reverse Linked List II where we bubble out the iter to the end of the group we're reversing, the start pointer will then become the iter (last element in the previous group after reversion), while we move iter to the next group.