61 - Rotate List

Rotate List

Problem

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

Examples

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]

Solution

/**
 * 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) {
        // Find size and store indices
        std::unordered_map<int, int> map;
        int N = 0;
        {
            ListNode *current = head;
            while (current != nullptr) {
                map[N] = current->val;
                current = current->next;
                ++N;
            }
        }
        // If full rotaton, return
        // x % 0 is UB
        const auto offset = N == 0 ? 0 : k % N;
        if (offset == 0) {
            return head;
        }
 
        // Otherwise walk along and find result
        {
            ListNode *current = head;
            int i = 0;
            while (current != nullptr) {
                current->val = map[(N - offset + i) % N];
                current = current->next;
                ++i;
            }
        }
        return head;
    }
};