1. 原題鏈接：https://leetcode.com/problems/rotate-list/
2. 解題思路
- 對于鏈表涉及到反轉、倒置等操作，一般都需要兩個指標：prev、cur
- 根據翻轉的規則，當翻轉次數剛好是鏈表長度list_len的整數倍時，實際上翻轉后的鏈表和未翻轉的原鏈表是一樣的
- 翻轉次數k >= 0，由于k的大小不確定，當k是list_len的整數倍時，直接回傳（因為通過k次翻轉后，還是和原鏈表一樣）；否則，實際需要翻轉的次數times是：（k % list_len）
- 因此，prev指向第(list_len - times)個節點，cur指向第(list_len - times + 1)個節點
- 采用頭插法將cur指向的鏈表插入到原鏈表的頭部
3. 演算法
- 統計鏈表長度為list_len
- 判斷k是不是list_len的整數倍
- 確定prev指標的位置，也就是第(list_len - times)個節點
- 確定cur指標的位置，也就是prev->next指向的節點
- 找到原鏈表的尾節點tail
- 采用頭插法進行翻轉
4. 實作
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;
int list_len = 0;
for(ListNode *tmp = head; tmp != NULL; tmp = tmp->next){
list_len++;
}
if(k % list_len == 0) return head;
int end = list_len - (k % list_len);
ListNode *prev = head;
for(int i = 1; i < end; i++){
prev = prev->next;
}
ListNode *cur = prev->next;
ListNode *tail = cur;
while(tail != NULL && tail->next != NULL){
tail = tail->next;
}
prev->next = tail->next;
tail->next = head;
return cur;
}
};
//tricky solution
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(head == NULL) return head;
int list_len = 1;
ListNode *tail = head;
for(; tail->next != NULL; tail = tail->next){
list_len++;
}
if(k % list_len == 0) return head;
int end = list_len - (k % list_len);
ListNode *prev = head;
for(int i = 1; i < end; i++){
prev = prev->next;
}
ListNode *cur = prev->next;
tail->next = head; //tricky: 首尾相連，構成環
prev->next = NULL; //prev也就是翻轉后鏈表的尾節點，因此從此處將環打開
return cur;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88241.html
標籤：其他