上期，小莱给大家分享了利用双指针定位删除节点及尾节点位置的方法（见《图解：删除链表倒数第N个节点》）。这期，小莱继续给大家分享一道利用双指针处理的链表拓展题。
题目：
给定一个链表，旋转链表，将链表每个节点向右移动 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
画外音：Leetcode第61题，中等/难度，通过率40.6% ！！！
下图为链表分别向右旋转2、3、4个位置后的情况。
经过观察，我们不难发现：
k=2时, 链表从位置3节点后分成两部分；
k=3时, 链表从位置2节点后分成两部分；
k=4时, 链表从位置1节点后分成两部分。
然后尾节点指向头节点就可以实现链表的旋转。
那么，这道看似旋转的题就很简单了，我们可以将其分为三步：
找到分段节点位置；
从分段节点后断开；
将尾节点指向头节点。
头节点位置是已知的，分段节点位置(位置3/位置2等)如何获取呢？
根据初始状态图：
位置3节点指向倒数第k=2个节点；
位置2节点指向倒数第k=3个节点；
位置1节点指向倒数第k=4个节点。
《图解：删除链表倒数第N个节点》里提到的前后双指针方法在这里就可以派上用场了。
画外音：为了与Leetcode保持一致，在这里没有使用单链表基础知识里实现的链表结构(主要区别在哨兵节点)。
可能有人发现了，这里的k值都是小于链表长度的。那么当k大于等于链表长度时，如何定位分段节点位置呢？
由上图可以看出：
当k为链表长度的倍数时，链表是维持原状的。当k为非倍数时，分段节点位置为len-(k%len)，指向倒数第k%len个节点。
那么问题就迎刃而解了！！！
代码实现：
struct ListNode* rotateRight(struct ListNode* head, int k){ if (head == NULL || head->next == NULL || k == 0) { return head; } struct ListNode* p,*q,*newHead,*tmp = head; int len,i; len = i = 0; // 求出链表长度 while (tmp != NULL) { tmp = tmp->next; len++; } k = k % len; // k为链表长度倍数时旋转后还是原位置 if (k == 0) { return head; } p = q = (struct ListNode*)malloc(sizeof(struct ListNode)); p->next = head; q->next = head; while(i < k) { q = q -> next; i++; } while (q->next != NULL) { q = q -> next; p = p -> next; } newHead = p->next; p->next = NULL; q->next = head; return newHead; }既然最终会将头节点指向尾节点，我们能不能一开始就把链表首尾相连，找到分段位置，将其断开呢？
那么我们的操作顺序就变为了：
链表首尾相连；
找到分段位置；
从分段节点后断开。
代码实现：
struct ListNode* rotateRight(struct ListNode* head, int k){ if (head == NULL || head->next == NULL) { return head; } struct ListNode *q,*p = head; int len = 1; // 求出链表长度 while (p->next != NULL) { p = p->next; len++; } p->next = head; // 链表首尾相连成环 p = head; k = len - (k % len); while (k > 0 && p != NULL) { q = p; // 新尾节点 p = p->next; // 新头结点 k--; } q->next = NULL; return p; }其实，这种方式与上边的方法在本质上是没有区别的，只是将首尾相连的操作前置了。不过可以作为一种解题思路。
1、本文中介绍了两种旋转链表的方式：
先分段后连接：将链表先从分段节点后分割开，然后首尾连接起来；
先连接后分段：将链表先首尾连接起来，再从分段节点后分割开。
2、分段节点位置计算方式为len-(k % len)，所指向节点位置计算方式为k%len。
看你骨骼清奇，天赋异禀！
送你一份大厂面试秘籍！
关注公众号「IT界农民工」回复「面试」即可获取！
作者：大家好，我是莱乌，BAT搬砖工一枚。从小公司进入大厂，一路走来收获良多，想将这些经验分享给有需要的人，因此创建了公众号「IT界农民工」。定时更新，希望能帮助到你。
《图解：链表基础知识及反转》
《图解：链表环的问题》
《图解：删除链表倒数第N个节点》
