题目：
给定一个链表，旋转链表，将链表每个节点向右移动 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
解法:
算法实现很直接：
（1）找到旧的尾部并将其与链表头相连old_tail->next = head，整个链表闭合成环，同时计算出链表的长度n；
（2）找到新的尾部，第(n-k%n-1)个节点，新的链表头是第(n-k%n)个节点；
（3）断开环new_tail->next = NULL， 并返回新的链表头new_head;
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* rotateRight(ListNode* head, int k) { 12 // base cases 13 if (NULL == head || NULL == head->next) 14 { 15 return head; 16 } 17 18 // close the linked list int the circle 19 ListNode *old_tail = head; 20 int n = 1; 21 while (old_tail->next != NULL) 22 { 23 old_tail = old_tail->next; 24 n++; 25 } 26 old_tail->next = head; 27 28 // find new tail: (n - k % n -1)th node 29 // and new head: (n -k % n)th node 30 ListNode *new_tail = head; 31 for (int i = 0; i < n -k % n - 1; i++) 32 { 33 new_tail = new_tail->next; 34 } 35 ListNode *new_head = new_tail->next; 36 37 // break the ring 38 new_tail->next = NULL; 39 40 return new_head; 41 42 } 43 };
原文：https://www.cnblogs.com/ocpc/p/12814915.html