61

61. Rotate List (Medium)

Given the head of a linked list, rotate the list to the right by k places.

 

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

 

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

Companies:
Microsoft, Amazon, Bloomberg

Related Topics:
Linked List, Two Pointers

Similar Questions:

• Rotate Array (Medium)
• Split Linked List in Parts (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/rotate-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    int getLength(ListNode *head) {
        int ans = 0;
        for (; head; head = head->next) ++ans;
        return ans;
    }
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return nullptr;
        int len = getLength(head);
        k %= len;
        if (k == 0) return head;
        auto p = head, q = head;
        while (k--) q = q->next;
        while (q->next) p = p->next, q = q->next;
        auto ans = p->next;
        p->next = nullptr;
        q->next = head;
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/rotate-list/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return nullptr;
        int len = 1;
        auto p = head;
        while (p->next) p = p->next, ++len;
        p->next = head;
        k = len - k % len;
        while (k--) p = p->next;
        auto ans = p->next;
        p->next = nullptr;
        return ans;
    }
};