Reverse LL in group of given size K
Amazon
MakeMyTrip
MetaSASigmoid AnalyticsThe problem
Given the head of a singly linked list containing integers, reverse the nodes of the list in groups of k and return the head of the modified list. If the number of nodes is not a multiple of k, then the remaining nodes at the end should be kept as is and not reversed.
Do not change the values of the nodes, only change the links between nodes.
Input: head -> 1 -> 2 -> 3 -> 4 -> 5, k = 2 Output: head -> 2 -> 1 -> 4 -> 3 -> 5 Explanation: The groups 1 -> 2 and 3 -> 4 were reversed as 2 -> 1 and 4 -> 3.
Input: head -> 1 -> 2 -> 3 -> 4 -> 5, k = 3 Output: head -> 3 -> 2 -> 1 -> 4 -> 5 Explanation: The groups 1 -> 2 -> 3 were reversed as 3 -> 2 -> 1. Note that 4 -> 5 was not reversed.
Input: head -> 6 -> 1 -> 2 -> 3 -> 4 -> 7, k = 4
- 1 <= k <= number of nodes in the linked list <= 105
- -104 <= ListNode.val <= 104
cpp
/*
Definition of singly linked list:
struct ListNode
{
int val;
ListNode *next;
ListNode()
{
val = 0;
next = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
}
ListNode(int data1, ListNode *next1)
{
val = data1;
next = next1;
}
};
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
}
};java
/*Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
}
}python
# Definition of singly linked list:
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head, k):javascript
/*Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
*/
class Solution {
reverseKGroup(head, k) {
}
}csharp
/*Definition of singly linked list:
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) {
}
}go
func reverseKGroup(head *ListNode, k int) *ListNode {
}Stuck? Show a way to structure it+
- 01Locate the kth node before modifying the current group.
- 02If fewer than k nodes remain, connect the remainder unchanged and stop.
- 03Reverse exactly the current group and reconnect it to the previous and next groups.
- 04Advance to the old group head and leave a final incomplete group unchanged.
Reference answer
Then expect these follow-ups
How would the logic change if the final partial group should also be reversed?
Tests: requirements
Can you implement it recursively, and what space does that use?
Tests: alternative design
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question