In the Leetcode Reverse Nodes in k-Group problem solution 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.
Constraints:
The number of nodes in the list is n.
1 <= k <= n <= 5000
0 <= Node.val <= 1000
Solution in C Programming
struct ListNode*
reverseK(struct ListNode *start, int k, struct ListNode **head) {
struct ListNode *prev = NULL;
struct ListNode *next = start->next;
for (int i = 0; i < k; i++) {
next = start->next;
start->next = prev;
prev = start;
start = next;
}
*head = prev;
return start;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
if (head == NULL || k == 0 || k == 1) {
return head;
}
int len = 0;
struct ListNode *cur = head;
while (cur) {
len++;
cur = cur->next;
}
int iters = len / k;
struct ListNode **prev = &head;
struct ListNode *tail = NULL;
struct ListNode *start = head;
for (int i=0; i<iters; i++) {
tail = start;
start = reverseK(start, k, prev);
tail->next = start;
prev = &(tail->next);
}
return head;
}Solution in C++ Programming
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
return reverseLinkedListInKGroup(head,k);
}
public:
ListNode* reverseLinkedListInKGroup(ListNode* head,int k){
if(head==NULL)
return head;
ListNode* curr = head;
int currLength=1;
while(curr->next!=NULL&& currLength<k){
curr=curr->next;
currLength+=1;
}
if(currLength<k){
return head;
}
ListNode* tempNode = curr->next;
curr->next=NULL;
ListNode* prev=NULL;
curr= head;
while(curr!=NULL){
ListNode* temp=curr->next;
curr->next=prev;
prev=curr;
curr=temp;
}
ListNode*tempList= reverseLinkedListInKGroup(tempNode,k);
head->next= tempList;
return prev;
}
};Solution in Java Programming
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null) return head; // single element doesnt need reversing
ListNode dummy = new ListNode();
dummy.next = head;
ListNode cur=dummy, nex=dummy, pre= dummy;
int count=0; //length of list
while(cur.next != null){
count++; cur = cur.next;
}
int groups= count/ k;
while( groups-- >0){
cur = pre.next; //cur at 1st node in k group
nex = cur.next; // at 2nd of the grp
//pre will be at previous node of that previous grp.
//now we will reverse k-1 links
for(int i=1 ; i<k ; i++){
//1->2->3 cur at 1, next at 2, pre is before 1.
cur.next = nex.next; //1->3
nex.next = pre.next; //2->1
pre.next = nex; //pre at 2
nex = cur.next; // nex at 3
}
pre = cur;
}
return dummy.next;
}
}Solution in Python Programming
class Solution(object):
def reverseKGroup(self, head, k):
# method to reverse k nodes in the list
def reverse(ls, k1):
prev = None
while ls and k1 > 0:
temp = ls.next
ls.next = prev
prev = ls
ls = temp
k1 -= 1
return prev, ls
temp1 = head
dummy = ListNode(0)
dum = dummy
while temp1:
temp2 = temp1
count = 0
# check if we have sufficient remaining nodes
while count < k and temp2:
temp2 = temp2.next
count += 1
if count == k:
# if k nodes are present then reverse those nodes
dummy.next, temp1 = reverse(temp1, k)
#move till the end of the dummy node for next iteration
while dummy.next:
dummy = dummy.next
else:
# if we don't have enough remaining nodes the merge it with the reversed nodes
dummy.next = temp1
break
return dum.nextSolution in C# Programming
public class Solution {
public ListNode ReverseKGroup(ListNode head, int k) {
if (head == null)
{
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
int count = 0;
ListNode pre = dummy;
ListNode cur = head;
while (cur != null)
{
count++;
ListNode next = cur.next;
if (count == k)
{
pre = reverse(pre, next);
count = 0;
}
cur = next;
}
return dummy.next;
}
private ListNode reverse(ListNode pre, ListNode end)
{
if (pre == null || pre.next == null)
return pre;
ListNode head = pre.next;
ListNode cur = pre.next.next;
while (cur != end)
{
ListNode next = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = next;
}
head.next = end;
return head;
}
}Also read,