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