图解：如何旋转链表
共 2739字，需浏览 6分钟
· 2020-09-07
前言
题目：
示例 1：
解释：
向右旋转 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。
文章整体目录
如何获取
很简单，在我的微信公众号 帅地玩编程 回复 程序员内功修炼 即可获取《程序员内功修炼》第一版和第二版的 PDF。
推荐，推荐一个 GitHub，这个 GitHub 整理了几百本常用技术PDF，绝大部分核心的技术书籍都可以在这里找到，GitHub地址：https://github.com/iamshuaidi/CS-Book（电脑打开体验更好），地址阅读原文直达