C++程序旋转链表

介绍

旋转链表是指将链表中的每个节点向右移动 k 个位置，其中 k 是非负数。

例如，将链表 1->2->3->4->5 向右旋转 2 个位置，得到的结果为 4->5->1->2->3。

在本文中，我们将介绍如何使用C++实现旋转链表。

方法

我们可以先将链表形成一个环，然后根据要旋转的个数，断开这个环，使得新的头节点指向旋转后的链表。

例如，对于链表 1->2->3->4->5、k=2，我们可以先形成一个环：1->2->3->4->5->1，然后将3->4->5->1(这个可以用k来求)断开，得到的新链表为 4->5->1->2->3。

对于如何形成一个环，我们可以先遍历找到链表的尾节点，然后将其指向头节点。

对于如何断开环，我们可以先找到倒数第 k + 1 个节点，将其下一个节点设为新的头节点，该节点就是旋转后的尾结点，再将倒数第 k+1 个节点设为新的尾结点，将其下一个节点设为 NULL，即成功断开了环形链表。

不过，在实现之前我们还需要考虑链表是否为空以及 k 是否大于链表长度的情况。

整个旋转链表的程序可以分三步走，先处理 k 大于链表长度的情况，其次找到倒数第 k 个节点，最后完成链表分离和连接。

实现

“` c++
/**
* 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) return head; // 先处理head为空的情况
int len = 1; // 求出链表长度
ListNode *p = head, *q = head;
while (p->next) {
++len;
p = p->next;
}
k = len – k % len; // 等价于(k %= len) 且去掉多余的旋转，这里的 len 已经事先加了1
if (k == len) return head; // 如果k == len，则不用旋转
for (int i = 0; i < k; ++i) q = q->next; // q指向倒数第k个节点
p->next = head; // 首尾相连，形成环
head = q->next; // 新的头节点为q的下一个节点
q->next = NULL; // 断开环
return head;
}
};
“`