25. Reverse Nodes in k-Group
- Hardness: \(\color{red}\textsf{Hard}\)
- Ralated Topics:
Linked List、Recursion
一、題目
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 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]
Constraints:
- The number of nodes in the list is
n. 1 <= k <= n <= 50000 <= Node.val <= 1000
二、分析
- 經典的
ListNode問題，鏈表的後序遍歷，利用後序遍歷回傳值的特性並用recursion來完成這一題。
三、解題
1. Recursion
- Time complexity: \(O()\)
- Space complexity: \(O()\)
ListNode* reverseKGroup(ListNode* head, int k) {
int cnt = k;
ListNode* last = head;
while (cnt && last) {
last = last->next;
cnt--;
}
if (cnt == 0) {
last = reverseKGroup(last, k);
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* next = nullptr;
cnt = k;
while (cnt--) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = last;
head = prev;
}
return head;
}