LeetCode 61. Rotate List

Solution1：我的答案 复杂度 O(n) O ( n ) ，还有一种复杂度为 O(1) O ( 1 ) 的算法 注意一点，在处理之前，需要k对链表长度取模，否则时间会超时。 处理链表的思想就是，先串成串，再断开~

/** * 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) { int length = 0; struct ListNode* count = head; while (count) {count = count->next; length++;} if (length == 0 || length == 1) return head; k %= length; if (k == 0) return head; struct ListNode* cur = head, *temp_start = head, *temp_end = head; while (temp_end->next) temp_end = temp_end->next; for (int i = 0; i < k; i++) { temp_end->next = temp_start; while (temp_start->next != temp_end) temp_start = temp_start->next; temp_start->next = NULL; struct ListNode* temp = temp_end; temp_end = temp_start; temp_start = temp; } return temp_start; } };

Solution2：我的答案 复杂度为 O(1) O ( 1 ) 的算法 参考网址：http://www.cnblogs.com/grandyang/p/4355505.html 相同的算法，别人实现起来就是简单好多~~~

class Solution { public: ListNode *rotateRight(ListNode *head, int k) { if (!head) return NULL; int n = 1; ListNode *cur = head; while (cur->next) { ++n; cur = cur->next; } cur->next = head; int m = n - k % n; for (int i = 0; i < m; ++i) { cur = cur->next; } ListNode *newhead = cur->next; cur->next = NULL; return newhead; } };