旋转数组和链表
Rotate an array of n elements to the right by k steps. For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
题目大意:将数组右旋k步 解法一: 解法1:1.旋转整个数组: [1,2,3,4,5,6,7] => [7,6,5,4,3,2,1] 2.旋转前k个数:[7,6,5,4,3,2,1] => [5,6,7,4,3,2,1] 3.旋转后n-k个数:[5,6,7,4,3,2,1] => [5,6,7,1,2,3,4]
1 2 3 4 5 6 7 8 9 10 11 12 13
class Solution {public : void (vector <int >& nums, int k) { if (k <= 0 || nums.size() <= 0 ) return ; k = k % nums.size(); reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin() + k); reverse(nums.begin() + k, nums.end()); } };
另外的解法参考:
Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. 解法,首尾相连,头部向前移动len(List) - k % len(List)步
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
* 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 == NULL || head->next == NULL || k == 0 ) return head; ListNode *prev = head; int len = 1 ; while (prev->next != NULL ){ prev = prev->next; len++; } k = len - k % len; prev->next = head; while (k > 0 ){ prev = prev->next; k--; } head = prev->next; prev->next = NULL ; return head; } };
近期评论