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;
    }
};