8000 added 110. Rotate List · VeaLang/LeetCode@069036c · GitHub
[go: up one dir, main page]
Skip to content

Commit 069036c

Browse files
pezypezy
committed
added 110. Rotate List
1 parent 5eda7cd commit 069036c

File tree

3 files changed

+87
-0
lines changed

3 files changed

+87
-0
lines changed

‎110. Rotate List/README.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
```cpp
2+
|
3+
1->2->3->4->5->NULL | ListNode *slow = head, *fast = head;
4+
^ ^ | while (k--) {
5+
slow fast ---> | if (fast == NULL) fast = head; // [1]
6+
|_____| | fast = fast->next;
7+
k | }
8+
| if (fast == NULL) return head;
9+
1->2->3->4->5->NULL | while (fast->next) {
10+
^ ^ ^ | fast = fast->next;
11+
head slow fast | slow = slow->next;
12+
|_____| | }
13+
k | List *new_head = slow->next;
14+
| slow->next = NULL;
15+
| fast->next = head;
16+
| return new_head;
17+
```
18+
19+
唯一要注意的在于:
20+
21+
[1]: 如果 k > linklist.size(n) 怎么办？
22+
23+
用示例来表示到底什么叫 rotate the list to the right by `k` places.
24+
25+
| k | origin | after |
26+
|:-:|:------:|:-----:|
27+
| 1 |0->1->2 |2->0->1|
28+
| 2 |0->1->2 |1->2->0|
29+
| 3 |0->1->2 |0->1->2|
30+
| 4 |0->1->2 |2->0->1|
31+
32+
可以观察的出来，当 k > n 的时候，`k = k % n`.
33+
34+
参考资料：[what to do when k is greater than size of list ?](https://oj.leetcode.com/discuss/2353/what-to-do-when-k-is-greater-than-size-of-list)

‎110. Rotate List/main.cpp

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
4+
using namespace std;
5+
6+
ListNode *create_linkedlist(std::initializer_list<int> lst)
7+
{
8+
auto iter = lst.begin();
9+
ListNode *head = lst.size() ? new ListNode(*iter++) : NULL;
10+
for (ListNode *cur=head; iter != lst.end(); cur=cur->next)
11+
cur->next = new ListNode(*iter++);
12+
return head;
13+
}
14+
15+
int main()
16+
{
17+
Solution s;
18+
ListNode *head = s.rotateRight(create_linkedlist({1,2,3,4,5}), 6);
19+
for (ListNode *cur=head; cur; cur=cur->next)
20+
std::cout << cur->val << "->";
21+
std::cout << "\b\b " << std::endl;
22+
23+
return 0;
24+
}
25+

‎110. Rotate List/solution.h

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
#include <cstddef>
2+
3+
struct ListNode {
4+
int val;
5+
ListNode *next;
6+
ListNode(int x) : val(x), next(NULL) {}
7+
};
8+
9+
class Solution {
10+
public:
11+
ListNode *rotateRight(ListNode *head, int k) {
12+
if (head == NULL || k == 0) return head;
13+
ListNode *slow = head, *fast = head;
14+
while (k--) {
15+
if (fast == NULL) fast = head;
16+
fast = fast->next;
17+
}
18+
if (fast == NULL) return head;
19+
while (fast->next) {
20+
fast = fast->next;
21+
slow = slow->next;
22+
}
23+
ListNode *new_head = slow->next;
24+
slow->next = NULL;
25+
fast->next = head;
26+
return new_head;
27+
}
28+
};

0 commit comments

Comments
 (0)
0