#pragma warning(disable:4996)

#include <cstdio>
#include <Windows.h>
#include <tchar.h>

/*
	submit time : 4
		can not remember
	request :
		Given a list, rotate the list to the right by k places, where k is non-negative.

		For example:
		Given 1->2->3->4->5->NULL and k = 2,
		return 4->5->1->2->3->NULL.
*/

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

ListNode *rotateRight(ListNode *head, int k) {
	if (k == 0 || head == NULL) return head;

	// get the list length
	ListNode* pNode = head;
	int length = 0;
	while (pNode != NULL) {
		++length;
		pNode = pNode->next;
	}
	if (length == 1) return head;
	k %= length;
	if (k == 0) k = length;

	ListNode* vernier = head;
	while (k--) {
		vernier = vernier->next;
		if (vernier == NULL) return head;
	}

	ListNode *newtail = head, *newhead = head;
	while (vernier->next != NULL) {
		newtail = newtail->next;
		vernier = vernier->next;
	}
	newhead = newtail->next;
	newtail->next = NULL;
	vernier->next = head;

	return newhead;
}