給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，其中 k 是非負數。

• 示例 1:

	輸入: 1->2->3->4->5->NULL, k = 2輸出: 4->5->1->2->3->NULL解釋:向右旋轉 1 步: 5->1->2->3->4->NULL向右旋轉 2 步: 4->5->1->2->3->NULL

• 示例 2:

	輸入: 0->1->2->NULL, k = 4輸出: 2->0->1->NULL解釋:向右旋轉 1 步: 2->0->1->NULL向右旋轉 2 步: 1->2->0->NULL向右旋轉 3 步: 0->1->2->NULL向右旋轉 4 步: 2->0->1->NULL

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (!head || k == 0) {return head;}// 計算鏈表的長度ListNode *p = head;int listSize = 0;while(p) {listSize ++;p = p->next;}// 計算偏移量，考慮為負數情況int move;if (k > 0) {move = k % listSize;} else {move = (k % listSize + listSize) % listSize;}if (move == 0 || move == listSize) {return head;}// 雙指針法找到要偏移的位置ListNode *p1 = head;ListNode *p2 = head;for (int i=0; i<move; i++) {p2 = p2->next;}while(p2->next) {p2 = p2->next;p1 = p1->next;}// 截取最后的鏈表p2 = p1->next;p1->next = NULL;p1 = p2;while(p1->next) {p1 = p1->next;}// 將截取的鏈表放在頭部p1->next = head;head = p2;return head;}
};

先形成環，然后找到合適的位置斷開

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (!head || k == 0) {return head;}ListNode *p = head;int listSize = 1;while(p->next) {listSize ++;p = p->next;}if (k < 0) {k = k % listSize + listSize;} else {k = k % listSize;}if (k == 0 || k == listSize) {return head;}// 形成環p->next = head;p = head;for (int i=1; i<listSize-k; i++) {p = p->next;}head = p->next;p->next = NULL;return head;}
};