# 61 - Rotate List

這題的直觀想法就是要先找到

• 新 list 的 head

• 新 list 的 tail

就可以改變幾個 next，更新成目標 list。

/**
 * 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 || !head->next || k == 0) return head;

        // Calculate length of list
        ListNode *cur = head;
        int len = 0;

        while(cur) {
            len++;
            cur = cur->next;
        }

        // Determine the newHead
        k = k%len;
        if(k == 0) return head;

        ListNode *dummy = new ListNode(0);
        dummy->next = head;

        cur = head;
        ListNode* prev = dummy;
        for(int i=0; i<len-k; i++){
            cur = cur->next;
            prev = prev->next;
        }

        // Find the tail
        ListNode* tail = dummy;
        for(int i=0; i<len; i++)
            tail = tail->next;

        // Relink the list
        dummy->next = cur;
        prev->next = NULL;
        tail->next = head;

        // Return the result
        ListNode *newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

這段 code 跑起來的程度是： Runtime: 8 ms, faster than 95.60% of C++ online submissions for Rotate List. Memory Usage: 8.9 MB, less than 80.57% of C++ online submissions for Rotate List.

唯一美中不足的地方是，最後為了要把 old list 的 tail 接回 old list head，我又多找了一次 tail。其實可以在最前面算 len 的時候，就順便把 tail 接回去，程式碼如下：

/**
 * 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 || !head->next || k == 0) return head;

        // Calculate length of list
        ListNode *cur = head, *prev;
        int len = 1;

        while(cur->next) {
            len++;
            cur = cur->next;
        }

        // Determine the newHead
        k = k%len;
        if(k == 0) return head;

        // Link old list tail to old list head
        cur->next = head;

        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *newHead;

        cur = head;
        prev = dummy;
        for(int i=0; i<len-k; i++){
            cur = cur->next;
            prev = prev->next;
        }

        // Relink the list
        dummy->next = cur;
        prev->next = NULL;

        // Return the result
        newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};