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

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

/**
 * 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) {
    // time complexity: O(n)
    // space complexity: O(1)

    if (k == 0 || !head){
      return head;
    }

    int size = 0;
    ListNode* first = head;
    ListNode* last_node = head;
    while(first){
      if(first && nullptr == first->next){
	last_node = first;
      }
      first = first -> next;

      size ++;
    }

    // it will be the same linked_list after rotate `size` steps
    k = k % size;
    if(k ==0){
      return head;
    }

    // split the linked list into two single linked lists by the rotate point;
    ListNode* k_minus_1 = head;
    for(int i = 0; i < size - k - 1; i++){
      k_minus_1 = k_minus_1 ->next;
    }

    ListNode* k_node = k_minus_1 -> next; // the rotate point
    k_minus_1 -> next = nullptr;
    last_node -> next = head;

    return k_node;
  }
};