leetcode Rotate List
來源：程序員人生 發布時間：2015-03-19 08:44:42 閱讀次數：3091次
1. 題目描寫
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.
2.解決方案1
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k)
{
if(head == NULL || k <= 0)
return head;
//get length
ListNode *temp = head;
int node_count = 0;
while(temp != NULL)
{
node_count++;
temp = temp->next;
}
if(k > node_count)
k = k%node_count;
if(k == node_count || k == 0)
return head;
//first node move k step
ListNode *first = head;
while( k > 0)
{
first = first->next;
k--;
}
//when first node move to last, the second node move (length - k) step
ListNode *second = head;
while(first->next != NULL)
{
first = first->next;
second = second->next;
}
ListNode *newhead = second->next;
//be a circle
first->next = head;
//broken circle
second->next = NULL;
return newhead;
}
};
思路：使用了快慢指針的技能。但由于k的值有可能大于全部的長度，所以還要先求出list的長度。先用快的指針走k步，然后再把它走到尾部，這個時候慢指針就走了length - k 的步數。再頭尾相連組成環，再斷環，返回新的頭部指針。
3.解決方案2
class Solution {
public:
ListNode* getLastNode(ListNode *head, int& len){
ListNode* node = head;
len = 1;
if(head == NULL){
len = 0;
return NULL;
}
while( node->next != NULL){
node = node->next;
len++;
}
return node;
}
ListNode *rotateRight(ListNode *head, int k) {
if(head == NULL){
return head;
}
int len;
ListNode* lastNode = getLastNode(head, len);
lastNode->next = head;
k %= len;
int step = len - k;
while(step>0){
lastNode = lastNode->next;
step--;
}
head = lastNode->next;
lastNode->next = NULL;
return head;
}
};
思路：先直接1個1個走到最后1個指針，然后連接成環，然后再行走lenght - k 的步數。再斷環。http://www.waitingfy.com/archives/1579
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
