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.
Test Cases
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]
Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseKGroup(struct ListNode* head, int k){
if (head == NULL) return head;
int count = 0;
struct ListNode* end = head;
while(count++ < k) {
if (end == NULL) return head;
end = end->next;
}
struct ListNode *next, *curr = head, *prev = reverseKGroup(end, k);
while(curr != end) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == NULL) return head;
int count = 0;
ListNode* end = head;
while(count++ < k) {
if (end == NULL) return head;
end = end->next;
}
ListNode *curr = head, *prev = reverseKGroup(end, k);
while(curr != end) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
};/**
* Definition for singly-linked list.
* 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) {
if (head == null) return head;
ListNode end = head;
int i = 0;
while(i++ < k) {
if (end == null) return head;
end = end.next;
}
ListNode prev = reverseKGroup(end, k), curr = head;
while(curr != end) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}from typing import Optional
# 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: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head:
return head
count, end = 0, head
while count < k:
if end is None:
return head
end = end.next
count += 1
curr, prev = head, self.reverseKGroup(end, k)
while curr != end:
next = curr.next
curr.next = prev
prev, curr = curr, next
return prev