# 25. Reverse Nodes in k-Group

## Description

Formatted question description: https://leetcode.ca/all/25.html

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 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

# Algorithm

To reverse a linked list in groups of size k, the process involves dividing the original linked list into several segments, each consisting of k nodes, and then individually reversing each segment. This operation necessitates two distinct functions: one for segmenting and another for reversing.

Consider the linked list 1->2->3->4->5 as an example. A common practice in linked list manipulations is to prepend a dummy node to the list. This is because the head of the list might change during the reversal process. The introduction of a dummy node ensures the head’s position is consistently trackable. Consequently, after adding a dummy node, the linked list becomes -1->1->2->3->4->5.

To reverse a group of nodes, for instance, nodes 1, 2, and 3 when k is 3, we employ two pointers: pre and next. The pre pointer indicates the node immediately preceding the group to be reversed, while next points to the node following the group. Post-reversal, the pre pointer advances to mark the new starting position for the next group reversal.

During each iteration for swapping a k-group, prev remains stationary, anchoring the start of the group being reversed, whereas current begins at node ‘1’ and moves through the group. Notably, for the duration of a single batch swap within the while (kcopy > 0) loop, prev does not shift:

Initial list: 1->2->3->4->5 , with k=3

After first step: 2->1->3->4->5
After full reversal: 3->2->1->4->5
Note: The 'next' node for 'prev' is continually updated to 'current’s next, hence 'current' remains unchanged in a single batch swap.


The time complexity is $O(n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the linked list.

# Code

• public class Reverse_Nodes_in_k_Group {

class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);

ListNode prev = dummy;

// count total nodes
int count = 0;
while (tmp != null) {
count++;
tmp = tmp.next;
}

// 1->2->3->4->5 , k=3
// 2,1,3,4,5
// 3,2,1,4,5
// => always getting 1's next for prev's next => current (below) not changing in one-batch-swap

// if only one node left, then no swap
while (count >= k) {

ListNode originalFirst = prev.next;

int kcopy = k - 1; // @note: since current node is already counted as 1
while (kcopy > 0) { // both prev and current, not changed in while loop

ListNode nextNextCopy = originalFirst.next.next;
ListNode firstInGroup = prev.next;

prev.next = originalFirst.next;
prev.next.next = firstInGroup;
originalFirst.next = nextNextCopy;

kcopy--;
}

// @note: update previous AND current. I forgot current...
prev = originalFirst; // now current is the last one of this group
count -= k;
}

return dummy.next;
}
}
}

//////

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy, cur = dummy;
while (cur.next != null) {
for (int i = 0; i < k && cur != null; ++i) {
cur = cur.next;
}
if (cur == null) {
return dummy.next;
}
ListNode t = cur.next;
cur.next = null;
ListNode start = pre.next;
pre.next = reverseList(start);
start.next = t;
pre = start;
cur = pre;
}
return dummy.next;
}

ListNode pre = null, p = head;
while (p != null) {
ListNode q = p.next;
p.next = pre;
pre = p;
p = q;
}
return pre;
}
}


• // OJ: https://leetcode.com/problems/reverse-nodes-in-k-group/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode h, *tail = &h;
auto prev = tail;
int i = 0;
for (auto p = head; i < k && p; ++i, p = p->next);
if (i < k) {
break;
}
for (int i = 0; i < k && head; ++i) {
node->next = prev->next;
prev->next = node;
}
while (tail->next) tail = tail->next;
}
return h.next;
}
};

• # 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: ListNode, k: int) -> ListNode:
'''
for reverse 1->2->3->4->5, process is like
1->None, 2->3->4->5
2->1->None, 3->4->5
3->2->1->None, 4->5
4->3->2->1->None, 5
5->4->3->2->1->None, None
'''
while p:
pnext = p.next
p.next = pre
pre = p
p = pnext
return pre

pre = cur = dummy
while cur.next:
for _ in range(k):
cur = cur.next
if cur is None:
return dummy.next
t = cur.next
cur.next = None # cut from next k-group, so to reverseList() for current k-group
start = pre.next
pre.next = reverseList(start)
start.next = t # so now 'start' is the last node of k-group
pre = cur = start # same as the reset dummy before while loop
return dummy.next

############

# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type k: int
:rtype: ListNode
"""

pre = None
while cur and k > 0:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
k -= 1
return cur, pre

length = 0
while p:
length += 1
p = p.next
if length < k:
step = length / k
ret = None
pre = None
while p and step:
if ret is None:
if pre:
pre = p
p = next
step -= 1
return ret


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
func reverseKGroup(head *ListNode, k int) *ListNode {
for i := 0; i < k; i++ {
if end == nil {
}
end = end.Next
}
res := reverse(start, end)
start.Next = reverseKGroup(end, k)
return res
}

func reverse(start, end *ListNode) *ListNode {
var pre *ListNode = nil
for start != end {
tmp := start.Next
start.Next, pre = pre, start
start = tmp
}
return pre
}


• /**
* class ListNode {
*     val: number
*     next: ListNode | null
*     constructor(val?: number, next?: ListNode | null) {
*         this.val = (val===undefined ? 0 : val)
*         this.next = (next===undefined ? null : next)
*     }
* }
*/

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
let dummy = new ListNode(0, head);
let pre = dummy;
let tail = pre;
for (let i = 0; i < k; ++i) {
tail = tail.next;
if (tail == null) {
return dummy.next;
}
}
let t = tail.next;
// set next
tail.next = t;
// set new pre and new head
pre = tail;
}
return dummy.next;
}

function reverse(head: ListNode, tail: ListNode) {
let pre = tail.next;
// head -> next -> ... -> tail -> pre
while (pre != tail) {
let t = cur.next;
cur.next = pre;
pre = cur;
cur = t;
}
}


• /**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int val=0, ListNode next=null) {
*         this.val = val;
*         this.next = next;
*     }
* }
*/
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy, cur = dummy;
while (cur.next != null)
{
for (int i = 0; i < k && cur != null; ++i)
{
cur = cur.next;
}
if (cur == null)
{
return dummy.next;
}
ListNode t = cur.next;
cur.next = null;
ListNode start = pre.next;
pre.next = ReverseList(start);
start.next = t;
pre = start;
cur = pre;
}
return dummy.next;
}

ListNode pre = null, p = head;
while (p != null)
{
ListNode q = p.next;
p.next = pre;
pre = p;
p = q;
}
return pre;
}
}

• // Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut pre = None;
while let Some(mut node) = head {
node.next = pre.take();
pre = Some(node);
}
pre
}

let mut dummy = Some(Box::new(ListNode::new(0)));
let mut pre = &mut dummy;
while cur.is_some() {
let mut q = &mut cur;
for _ in 0..k - 1 {
if q.is_none() {
break;
}
q = &mut q.as_mut().unwrap().next;
}
if q.is_none() {
pre.as_mut().unwrap().next = cur;
return dummy.unwrap().next;
}

let b = q.as_mut().unwrap().next.take();
pre.as_mut().unwrap().next = reverse(cur);
while pre.is_some() && pre.as_mut().unwrap().next.is_some() {
pre = &mut pre.as_mut().unwrap().next;
}
cur = b;
}
dummy.unwrap().next
}
}


• # Definition for singly-linked list.
# class ListNode {
#     public $val; # public$next;
#     public function __construct($val = 0,$next = null)
#     {
#         $this->val =$val;
#         $this->next =$next;
#     }
# }

class Solution {
/**
* @param ListNode $head * @param int$k
* @return ListNode
*/

function reverseKGroup($head,$k) {
$dummy = new ListNode(0);$dummy->next = $head;$prevGroupTail = $dummy; while ($head !== null) {
$count = 0;$groupHead = $head;$groupTail = $head; while ($count < $k &&$head !== null) {
$head =$head->next;
$count++; } if ($count < $k) {$prevGroupTail->next = $groupHead; break; }$prev = null;
for ($i = 0;$i < $k;$i++) {
$next =$groupHead->next;
$groupHead->next =$prev;
$prev =$groupHead;
$groupHead =$next;
}
$prevGroupTail->next =$prev;
$prevGroupTail =$groupTail;
}

return \$dummy->next;
}
}