Given a list, rotate the list to the right by k places, where k is non-negative.
Have you met this question in a real interview?
Yes
Example
Given
1->2->3->4->5
and k = 2
, return 4->5->1->2->3
.
贴一个错的答案,没有考虑超过长度的问题。。。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * @param head: the list * @param k: rotate to the right k places * @return: the list after rotation */ ListNode *rotateRight(ListNode *head, int k) { // write your code here if (!head || !head->next) return head; ListNode dummy(0); dummy.next=head; head=&dummy; for(int i=0;i<k;i++){ if (!head) return 0; head=head->next; } ListNode* slow=&dummy; while(head->next){ slow=slow->next; head=head->next; } ListNode* tmp=slow->next; slow->next=0; tmp->next=dummy.next; return tmp; } };
这个解得测试结果:
Input
17->75->80->87->44->45->75->86->74->20->null, 19
Output
null
Expected
75->80->87->44->45->75->86->74->20->17->null
所以需要一个余数,先算个n,不过写了半天还是有bug,一怒之下换个思路,用环,先把首位相连,然后再重新断开。。。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * @param head: the list * @param k: rotate to the right k places * @return: the list after rotation */ ListNode *rotateRight(ListNode *head, int k) { // write your code here if(!head || !head->next) return head; int count=1; ListNode* runNode=head; while(runNode->next){ count++; runNode=runNode->next; } runNode->next=head; runNode=head; for (int i=1; i<count-k%count; i++){ runNode=runNode->next; } head=runNode->next; runNode->next=0; return head; } };
No comments:
Post a Comment