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
. 首先从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的可能。