754
技術社區[雲棲]
[LeetCode]61.Rotate List
【題目】
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
【題意】
給定一個鏈表，向右旋轉k個位置，其中k是非負的。
【分析】
先遍曆一遍，得出鏈表長度 len，注意 k 可能大於 len，因此令 k% = len。將尾節點 next 指針
指向首節點，形成一個環，接著往後跑 len - k 步，從這裏斷開，就是要求的結果了。
【代碼1】
/*********************************
* 日期：2014-01-29
* 作者：SJF0115
* 題號: Rotate List
* 來源：https://oj.leetcode.com/problems/rotate-list/
* 結果：AC
* 來源：LeetCode
* 總結：
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
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 || k <= 0){
return head;
}
int count = 1;
ListNode *pre = head,*cur;
//統計節點個數，找到尾節點串成一個環
while(pre->next != NULL){
count++;
pre = pre->next;
}
//串成一個環
pre->next = head;
//k可能大於鏈表長度
k = k % count;
int index = 1;
pre = cur = head;
//右移k位
while(index <= (count - k)){
pre = cur;
cur = cur->next;
index++;
}
//新的首尾節點
pre->next = NULL;
head = cur;
return head;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5};
ListNode *head = (ListNode*)malloc(sizeof(ListNode));
head->next = NULL;
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 5;i++){
node = (ListNode*)malloc(sizeof(ListNode));
node->val = A[i];
node->next = NULL;
pre->next = node;
pre = node;
}
head = solution.rotateRight(head->next,6);
while(head != NULL){
printf("%d ",head->val);
head = head->next;
}
return 0;
}
【代碼2】
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if (head == NULL || k == 0)
return head;
int len = 1;
ListNode* p = head;
while (p->next) { // 求長度
len++;
p = p->next;
}
k = len - k % len;
p->next = head; // 首尾相連
for(int step = 0; step < k; step++) {
p = p->next; //接著往後跑
}
head = p->next; // 新的首節點
p->next = NULL; // 斷開環
return head;
}
};
【思路三】
/*-------------------------------------------------------------------
* 日期：2014-04-08
* 作者：SJF0115
* 題目: 61.Rotate List
* 來源：https://leetcode.com/problems/rotate-list/
* 結果：AC
* 來源：LeetCode
* 總結：
--------------------------------------------------------------------*/
#include <iostream>
using namespace std;
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 || k <= 0){
return head;
}//if
int size = 0;
ListNode *p = head,*right = head;
// 統計節點個數
while(p){
++size;
p = p->next;
}//while
// 找到右移的節點
k = size - k % size;
// 未右移
if(k == size){
return head;
}//if
ListNode *pre = nullptr;
for(int i = 0;i < k;++i){
pre = right;
right = right->next;
}//for
pre->next = nullptr;
p = right;
// 到最後一個節點
while(p->next){
p = p->next;
}//while
p->next = head;
return right;
}
};
int main() {
Solution solution;
int A[] = {1,2,3,4,5};
ListNode *head = new ListNode(-1);
ListNode *node;
ListNode *pre = head;
for(int i = 0;i < 5;i++){
node = new ListNode(A[i]);
pre->next = node;
pre = node;
}//for
head = solution.rotateRight(head->next,2);
while(head){
cout<<head->val<<" ";
head = head->next;
}//while
cout<<endl;
return 0;
}
運行時間：
最後更新：2017-04-03 12:54:51