61. Rotate List

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

主要利用兩個快慢pointers，記得處理input linkedlist是空的情形，還有k大於linkedlist本身的長度的情形。

// Two pointers
ListNode* rotateRight(ListNode* head, int k) { // time: O(n); space: O(1)
    if (!head) return nullptr;
    int n = 0;
    ListNode* cur = head;
    while (cur) { // calculate list length
        ++n;
        cur = cur->next;
    }
    k %= n; // handle the case if k is larger than list length
    // Use two pointers
    ListNode *slow = head, *fast = head;
    for (int i = 0; i < k; ++i) {
        fast = fast->next;
    }
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    fast->next = head;
    fast = slow->next;
    slow->next = nullptr;
    return fast;
}

不用2 pointers也可以完成這題。

// Connect the tail to head for rotation
ListNode* rotateRight(ListNode* head, int k) { // time: O(n); space: O(1)
    if (!head) return nullptr;
    int n = 1;
    ListNode *cur = head;
    while (cur->next) { // calculate list length
        ++n;
        cur = cur->next;
    }
    cur->next = head; // connect the tail to head for rotation
    int m = n - k % n;
    for (int i = 0; i < m; ++i) {
        cur = cur->next;
    }
    ListNode* newHead = cur->next;
    cur->next = nullptr;
    return newHead;
}

189. Rotate Array