LeetCode #61：Rotate List(旋转链表)

题目描述

思路不难，就是将链尾拆下来插到链首 k 次，类似于 “循环右移”。需要注意的是如果直接写循环 k 次会超时（题目中 k 的范围是 0 <= k <= 2 * 10⁹），这个时候的优化思路是统计一下链表的元素总数 count，再把循环次数设为 k 模 count，就能应对 k 很大但 count 很小的情况了（避免了大量重复的右移）。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        pHead = new ListNode(0, head);
        tail = pHead;

        if(head == NULL || head->next == NULL || k == 0) return head;

        int count = 0;
        for(ListNode* q = pHead; q->next != NULL; count++, q = q->next) {
            if(q->next->next == NULL) tail = q; //统计count的时候顺便把tail的位置也确定下来
        }  

        for(int i = 0; i < k % count; i++) { //循环k mod count次
            deleteAndPutHead();
            refreshTail();
        }

        return pHead->next;
    }

private:
    ListNode* pHead = NULL;
    ListNode* tail = NULL;

    void deleteAndPutHead() {
        auto p = tail->next;
        tail->next = NULL;
        p->next = pHead->next;
        pHead->next = p;
    }

    void refreshTail() {
        tail = pHead;
        while(tail->next->next != NULL) {
            tail = tail->next;
        }
    }
};