Rotate Array and Rotate List

Posted on   |   In   |  

旋转数组和链表

Rotate Array

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 rotate(vector<int>& nums, int k) {
        if(k <= 0 || nums.size() <= 0)
            return;
        //注意此处k对数组的长度取模，因为k有可能大于数组长度
        k = k % nums.size();
        
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

另外的解法参考:

http://www.cnblogs.com/vincently/p/4299924.html

Rotate List

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;
        //prev指向尾节点
        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;
    }
};