Rotate Array

原題鏈接Rotate Array

回轉一個給定數組k步，本質上是將后k個元素移動到前面（需要保證k小于數組元素個數）

不在原數組上操作的話比較簡單，新開一個vector保存回轉后的順序，然后copy到原數組上，時間和空間復雜度都是O(n)

如果需要在原數組上操作的話，就不能有額外的空間使用消耗。那么有如下技巧

將數組后k個元素逆序

將數組前n - k個元素逆序

將整個數組逆序

依次執行上述步驟就完成了回轉，以[1,2,3,4,5,6,7]為例，另k為3，那么

將后3個元素逆序，變為[1,2,3,4,7,6,5]

將前4個元素逆序，變為[4,3,2,1,7,6,5]

將整個數組逆序，變為[5,6,7,1,2,3,4]

解釋

• 對于數組的某個子部分，兩次逆序等于沒有改變，所以前n-k個元素和后k個元素這兩部分的內部順序不會被改變
• 對于數組的整體而言，只逆序了一次，相當于改變頭尾順序

代碼如下

class Solution { public:void rotate(vector<int>& nums, int k) {if(nums.empty() || k <= 0)return;int n = nums.size();/* 防止k大于n，這一步驟讓k小于n。因為回轉n次等于沒有回轉 */k %= n;std::reverse(nums.begin() + n - k, nums.end());std::reverse(nums.begin(), nums.begin() + n - k);std::reverse(nums.begin(), nums.end());} };

---

Rotate List

原題鏈接Rotate List

回轉鏈表，將后k個非空節點移動到表頭。
因為數組可以通過下標定位，所以可以進行三次逆序，但是鏈表不行，首先不知道鏈表中節點個數，其次不能夠直接定位到倒數第k個非空節點。

問題分兩步

• 確定非空節點個數
• 從頭找第n - k個節點，將其作為最后一個節點，第n - k + 1個節點作為表頭

代碼如下

/*** 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) {if(head == nullptr || k <= 0)return head;int n = 1;ListNode* tail = head;/* 確定非空節點個數以及最后一個非空節點 */while(tail->next){++n;tail = tail->next;}/* 另k小于n，如果k不為0，說明仍然需要回轉 */if(k %= n){/* 最后一個節點指向表頭tail->next = head;/* 找到第n-k個節點，因為head是第一個，所以i從1開始 */for(int i = 1; i < n - k; ++i)head = head->next;/* 第n-k+1個節點變為表頭，第n-k個節點變為末尾節點 */ListNode* res = head->next;head->next = nullptr;return res;}/* 如果k為0，說明不需要回轉，直接返回表頭 */else{return head;}} };

---

上面兩道題都是將后k個元素移動到前面

• 對于數組而言，無法像鏈表一樣只改變某幾個節點就實現了順序的改變。但是可以采用三次逆序的方式改變整體的順序，彌補缺陷
• 對于鏈表而言，無法像數組一樣直接確定元素個數和定位某個元素，需要分別求得才可以。但是可以通過改變某些節點以達到順序的改變
• 二者都需要考慮邊界條件，鏈表最為明顯，需要考慮表頭以及null節點。

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----将数组/链表后k个元素移动到前面的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。