开发者社区云计算文章正文

[LeetCode] Rotate List

2015-07-17 709

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Well, in the case of a linked list instead of an array, the problem becomes easier. We just need to find the node that will be the new head of the lis...

Well, in the case of a linked list instead of an array, the problem becomes easier. We just need to find the node that will be the new head of the list after the rotation and then restructure the list.

 1 class Solution {
 2 public:
 3     ListNode* rotateRight(ListNode* head, int k) {
 4         if (!head) return NULL;
 5         int len = listLength(head);
 6         k %= len;
 7         ListNode* fast = head;
 8         for (int i = 0; i < k; i++)
 9             fast = fast -> next;
10         ListNode* slow = head;
11         while (fast -> next) {
12             slow = slow -> next;
13             fast = fast -> next;
14         }
15         fast -> next = head;
16         head = slow -> next;
17         slow -> next = NULL;
18         return head;
19     }
20 private:
21     int listLength(ListNode* head) {
22         int len = 0;
23         while (head) {
24             len++;
25             head = head -> next;
26         }
27         return len;
28     }
29 };