Google+ Followers

Tuesday, January 1, 2013

[LeetCode] 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.
» Solve this problem

[解题思路]
首先从head开始跑,直到最后一个节点,这时可以得出链表长度len。然后将尾指针指向头指针,将整个圈连起来,接着往前跑len – k%len,从这里断开,就是要求的结果了。

[Code]
1:    ListNode *rotateRight(ListNode *head, int k) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      if(head == NULL || k ==0) return head;  
5:      int len =1;  
6:      ListNode* p = head,*pre;  
7:      while(p->next!=NULL)  
8:      {  
9:        p = p->next;  
10:        len++;      
11:      }  
12:      k = len-k%len;  
13:      p->next = head;  
14:      int step =0;  
15:      while(step< k)  
16:      {  
17:        p = p->next;  
18:        step++;  
19:      }  
20:      head = p->next;  
21:      p->next = NULL;  
22:      return head;  
23:    }  


[Note]
注意K大于len的可能。

Post a Comment