LeetCode 61. Rotate List | 翻转k次链表
翻转链表
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4 Output:2->0->1->NULL
Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right:0->1->2->NULL
rotate 4 steps to the right:2->0->1->NULL
- 链表长度=0,返回head
- 链表长度<=1,返回head
- 链表长度>1,如果k%count=0,返回head。(count表示链表长度)
- 其他情况,把后(k%count)个放到链表前面。
C++版本。
/**100% 100%
* 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) {
if(head==NULL) return head;
ListNode *tmp = head;
//计算链表长度
int count=1;
while(tmp->next){
tmp=tmp->next;
count++;
}
if(count<=1)return head;
if(k%count==0) return head;
//找到后面k个(要放前面)
int km = k%count;
int ktmp = km;
ListNode *fast = head;
ListNode *slow = head;
while(km>0){
fast = fast->next;
km--;
}
while(fast->next){
fast = fast->next;
slow = slow->next;
}
//后面部分
ListNode *tmp1 = new ListNode(0);
tmp1->next = slow->next;
ListNode *newhead=tmp1;
while(tmp1->next){
tmp1 = tmp1->next;
}
//前面部分
ListNode *tmp2 = new ListNode(0);
tmp2->next = head;
tmp1->next = tmp2->next;
while(ktmp<count){
tmp2 = tmp2->next;
ktmp++;
}
tmp2->next=NULL;
return newhead->next;
}
};