LeetCode 61. Rotate List（循环右移单链表）

题目描述：

    Given a list, rotate the list to the right by k places, where k is non-negative.

例子：

Given 1->2->3->4->5->NULL and k = 2,

return 4->5->1->2->3->NULL.

分析：

    题意：给定一个单链表，返回将它循环右移k（k是非负整型数）次的结果。

    思路：我们首先计算单链表的结点个数n。因为可能存在k > n的情况，先进行取模计算k = k % n。初始化指针pre = head、p = head、q = head。接下来分为三步走：① 将指针q往右移动k次；② 在指针q指向结点的next指针不为空时，同时向右移动指针pre和指针q，那么指针pre就指向了返回单链表首结点的前驱结点；③p = pre->next指向返回单链表的首结点，pre->next = NULL使得指针pre指向结点为新的尾结点，q->next = head进行重新连接，返回指针p即可 。
    时间复杂度为O(n)。

代码：

#include <bits/stdc++.h>

using namespace std;

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

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
		// Exceptional Case: 
        if(!head || !head->next || k == 0){
			return head;
		}
		// cnt
		int n = 0;
		ListNode *pre = head, *p = head, *q = head;
		while(p){
			n++;
			p = p->next;
		}
		k = k % n;
		// check important!
		if(k == 0){
			return head;
		}
		for(int i = 1; i <= k; i++){
			q = q->next;
		}
		while(q->next){
			pre = pre->next;
			q = q->next;
		}
		p = pre->next;
		pre->next = NULL;
		q->next = head;
		return p;
    }
};