Reverse Nodes In k-Group Problem: 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:
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]
Table of Contents
Reverse Nodes In k-Group Problem Solution
Problem Solution In Python
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
dummy_head=M_head=ListNode()
dummy_head.next=head
# Calculate Length
l=0
t=head
while t:
l+=1
t=t.next
# Get multiple length of k
l//=k
while head and l:
for _ in range(1,k):
temp=head.next
head.next=temp.next
temp.next=M_head.next
M_head.next=temp
if head:
M_head,head=head,head.next
l-=1
return dummy_head.next
Problem Solution In Java
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null) return head;
ListNode tail = head;
int movements = k;
while(tail != null && movements > 1){
tail = tail.next;
movements--;
}
if(tail == null) return head;
ListNode next = tail.next;
tail.next = null;
ListNode newHead = reverse(head);
head.next = reverseKGroup(next, k);
return newHead;
}
public ListNode reverse(ListNode head){
if(head == null || head.next == null) return head;
ListNode prev = null;
ListNode cur = head;
while(cur != null){
ListNode nextTemp = cur.next;
cur.next = prev;
prev = cur;
cur = nextTemp;
}
return prev;
}
Problem Solution In C++
class Solution {
public:
ListNode* reverse(ListNode* head) {
if(head==NULL || head->next==NULL)
return head;
ListNode* temp=reverse(head->next);
ListNode* newHead=temp;
while(temp->next!=NULL)temp=temp->next;
temp->next=head;
head->next=NULL;
return newHead;
}
ListNode* reverseKGroup(ListNode* head, int k) {
if(k==0 || head==NULL || head->next==NULL)
return head;
int cnt=k-1;
ListNode* tmp=head;
while(cnt && tmp->next!=NULL){
tmp=tmp->next;cnt--;
}
if(cnt!=0)
return head;
ListNode* t=reverseKGroup(tmp->next,k);
tmp->next=NULL;
ListNode* newHead=reverse(head);
tmp=newHead;
while(tmp->next!=NULL)
tmp=tmp->next;
tmp->next=t;
return newHead;
}
};
Problem Solution In C
struct ListNode* kSteps(struct ListNode* head, int k) {
for (int i = 1; i < k && head; i++)
if (head) head = head->next;
if (head) return head;
return NULL;
}
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
if (k < 2) return head;
struct ListNode* prev = kSteps(head, k);
if (prev) {
struct ListNode* next = head, * curr = head, * tail = curr;
head = prev;
prev = prev->next;
for (int i = 0; i < k; i++) {
next = next->next;
curr->next = prev;
prev = curr;
curr = next;
}
while (prev = kSteps(curr, k)) {
tail->next = prev;
tail = curr;
prev = prev->next;
for (int i = 0; i < k; i++) {
next = next->next;
curr->next = prev;
prev = curr;
curr = next;
}
}
}
return head;
}