Question

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

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.

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,

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

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



Algorithm

To reverse a linked list in groups of size k, we first need to divide the original linked list into several small segments, each containing k nodes, and then flip each segment separately. This requires two functions, one for segmentation and one for flipping.

For example, consider the linked list 1->2->3->4->5. When dealing with linked list problems, it’s common to add a dummy node at the beginning because the head node may change when the linked list is flipped. To keep track of the current latest position of the head node, we introduce a dummy node before the original head node. In this case, the linked list after adding the dummy node becomes -1->1->2->3->4->5.

To reverse the group of nodes 1, 2, and 3 when k is 3, we need two pointers: pre and next. pre points to the node before the group to be flipped, and next points to the node after the group to be flipped. After flipping the group, the position of pre is updated to the following new position.

prev is dummy, then current is always node ‘1’, ‘1’ will move each iteration of while loop for k-group swap

prev is static during the full while loop of while (kcopy > 0) // 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

Code

Java

• 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;
}
}
}


• // 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:
while p:
q = p.next
p.next = pre
pre = p
p = q
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
start = pre.next
pre.next = reverseList(start)
start.next = t
pre = start
cur = pre
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: