LeetCode Rotate List 分析解答
看了很多热心人的推荐，觉得LeetCode应该也是个不错的练习算法的地方。
问题：
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.
看起来非常简单的问题，但是试了几次才Accepted，归结其耗时的原因是：
1 . 匆忙解答，思路不系统（尤其是对看起来简单的问题，最容易犯的毛病）；
2. 没有系统分析特殊情况
LeetCode的Online Judge系统还是不错的，测试用例很全，所以，有一点东西没考虑到都会被rejected的。
下面是解答程序，应该都注释好了，看起来算清晰了吧：
#include
using namespace std;
//Definition for singly-linked list.
struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};class Solution {
public:ListNode *rotateRight(ListNode *head, int k) {//Special treatmentif(head==NULL)return NULL; //initialization variablesListNode *cur = head;ListNode *pre = head;int i = 1, j = 1;//1. Normal situationfor(; cur->next!=NULL; i++, cur=cur->next){if((i-j)==k){j++;pre=pre->next;}}//2. special situation1if(i==k) return head;//3. special situation2if(k>i){k%=i;while ((i-j)!=k){j++;pre=pre->next;}}//connect new linkcur->next = head;head = pre->next;pre->next = NULL;return head;}
};int main()try
{{ListNode head(11);ListNode fir(1);ListNode sec(2);ListNode thi(3);ListNode fou(4);ListNode fiv(5);ListNode six(6);ListNode sev(7);ListNode eig(8);ListNode nin(9);ListNode ten(10);head.next = &fir;fir.next = &sec;sec.next = &thi;thi.next = &fou;fou.next = &fiv;fiv.next = &six;six.next = &sev;sev.next = &eig;eig.next = &nin;nin.next = &ten;ten.next = NULL;ListNode *pn(NULL);pn = &head;for(; pn!=NULL; ){cout<val<<" ";pn=pn->next;}cout<val<<" ";pn=pn->next;}cout<
看来算法的提高真是任重而道远！
//2014-1-30 updateListNode *rotateRight(ListNode *head, int k) {if (!head || !head->next) return head;ListNode dummy(-1);dummy.next = head;ListNode *pre = &dummy;int n = getListLength(head);k %= n;for (k--; k && head->next; k--) head = head->next;while (head->next){head = head->next;pre = pre->next;}ListNode *h = pre->next;pre->next = nullptr;head->next = dummy.next;return h;}int getListLength(ListNode *h){int len = 0;for ( ; h; h = h->next) len++;return len;}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！