[LeetCode] 61. Rotate List 旋轉(zhuǎn)鏈表
Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4
Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 109
這道旋轉(zhuǎn)鏈表的題和之前那道 Rotate Array 很類似，但是比那道要難一些，因為鏈表的值不能通過下表來訪問，只能一個一個的走，博主剛開始拿到這題首先想到的就是用快慢指針來解，快指針先走k步，然后兩個指針一起走，當(dāng)快指針走到末尾時，慢指針的下一個位置是新的順序的頭結(jié)點，這樣就可以旋轉(zhuǎn)鏈表了，自信滿滿的寫完程序，放到 OJ 上跑，以為能一次通過，結(jié)果跪在了各種特殊情況，首先一個就是當(dāng)原鏈表為空時，直接返回NULL，還有就是當(dāng)k大于鏈表長度和k遠遠大于鏈表長度時該如何處理，需要首先遍歷一遍原鏈表得到鏈表長度n，然后k對n取余，這樣k肯定小于n，就可以用上面的算法了，代碼如下:
解法一：
|
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
|
class Solution {public: ListNode *rotateRight(ListNode *head, int k) { if (!head) return NULL; int n = 0; ListNode *cur = head; while (cur) { ++n; cur = cur->next; } k %= n; ListNode *fast = head, *slow = head; for (int i = 0; i < k; ++i) { if (fast) fast = fast->next; } if (!fast) return head; while (fast->next) { fast = fast->next; slow = slow->next; } fast->next = head; fast = slow->next; slow->next = NULL; return fast; }}; |
這道題還有一種解法，跟上面的方法類似，但是不用快慢指針，一個指針就夠了，原理是先遍歷整個鏈表獲得鏈表長度n，然后此時把鏈表頭和尾鏈接起來，在往后走 n - k%n 個節(jié)點就到達新鏈表的頭結(jié)點前一個點，這時斷開鏈表即可，代碼如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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; }}; |
到此這篇關(guān)于C++實現(xiàn)LeetCode(61.旋轉(zhuǎn)鏈表)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)旋轉(zhuǎn)鏈表內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://www.cnblogs.com/grandyang/p/4355505.html
