61. Rotate List

发表于 | 分类于

每日一题 2019 - 04 - 04

题目：

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

解法：

这个题让我们将链表中的元素往前推 K 位，其实就是等于将数组中的元素往后移动，思路很简单，创立中间 vector，将 vector 移动完成后，重新赋值给链表；

不过要注意一点，移动的步数 K 一定要记得对数组的长度取模，不然就是超时！

代码：

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
36
37
38
39
/**
 * 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)
        {
            return head ;
        }
        ListNode *temp = head ;
        vector<int> now ;
        while( temp != NULL )
        {
            now.push_back(temp->val);
            temp = temp -> next ;
        }
        k = k % now.size() ;
        for(int i = 0 ; i < k ; i ++ )
        {
            int tem = now[now.size()-1] ;
            for (int j = now.size() - 2 ; j >= 0 ; j -- )
                now[j+1] = now[j];
            now[0] = tem ;
        }
        temp = head ;
        for(int j = 0 ; j < now.size() ; j ++ )
        {
            temp -> val = now[j] ;
            temp = temp -> next ;
        }
        return head ;
    }
};
0%
undefined