#include <stdio.h>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x=0) : val(x), next(NULL) {}
};

//move top k nodes to the tail of linked list
ListNode * RotateLeft(ListNode *head, ListNode *tail, int k)
{
    if(k <=0 )return head;
    ListNode * p = head;

    while(--k > 0)p = p->next;

    tail->next = head;
    head = p->next;
    p->next = NULL;

    return head;
}

ListNode * RotateRight(ListNode *head, int k)
{
    if (head == NULL)return head;
    
    int length = 1;
    ListNode* p = head;
    while(p->next != NULL) p = p->next, ++length;

    k = k % length;

    //rotate to the right by k is identical to rotate to the left by (length - k);
    return RotateLeft(head, p, length - k);
}

int main(int argc, char** argv)
{
    ListNode nodes[21];
    for (int i = 0; i < 20; ++i)
    {
        nodes[i].val = i+1;
        nodes[i].next = nodes+i+1;
    }
	nodes[20].val = 21;
	
    ListNode* head = RotateRight(nodes, 147);

   while(head)
   {
        printf("%d,", head->val);
        head = head->next;
   }

    return 0;
}