25. Reverse Nodes in k-Group
1.問題
給予一個linked list, 回傳k組排序的結果

2.想法
提問
function header, parameter
test inpu
說明想法
遞迴作法:
base case: 不到k個node的話, return head
將next = curr->next
curr-> next 接到前一組k group排序的結果
排序當前的k group
測試計算複雜度: O(n)
3.程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
//base case: 如果數目不到k, 回傳head
ListNode* next = head;
int i = 0;
while (next && i < k) {
next = next->next;
i++;
}
if (i < k) {
return head;
}
//pre為上一組k group的頭
ListNode* pre = reverseKGroup(next, k);
//reverse當前的k group
ListNode* curr = head;
for (int i = 0; i < k; i++) {
next = curr->next;
curr->next = pre;
pre = curr;
curr = next;
}
return pre;
}
};
Last updated