61. Rotate List
1.問題
給予一個list, 讓list旋轉k格

2.想法
提問
parameter
test input
觀察
旋轉後將會讓第(n - k)個node為新的head
說明想法
先create新的ptr並移動到尾部, 讓list的尾部接到頭部, 形成cycle, 移動last向前 (n - k), 新的head即為last->next, 並讓last->next = NULL
測試計算複雜度
3.程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
while (!head) {
return head;
}
int index = 0, cnt = 1;
ListNode* last = head, *newHead = 0;
while (last->next) {
last = last->next;
cnt++;
}
last->next = head;
k = (k % cnt);
for (int i = 0 ; i < (cnt - k); i++) {
last = last->next;
}
newHead = last->next;
last->next = NULL;
return newHead;
}
};
Last updated