旋转链表——快慢指针法的实践

一、题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 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

二、分析

根据题目给出的示例，可以总结出：将链表中每个节点向右移动K个位置，也就是将链表中倒数第K个节点作为头节点，其前面的所有节点放在原链表尾节点之后。

因此整体思路就是找到倒数第K个节点的前一个节点，然后让链表首尾相连，第K个节点作为链表旋转后的新的头节点，其前一个节点作为链表旋转后的尾节点。

接下来，我们逐步看下具体过程。

示例1给出的链表结构如下图所示：

首先，定义慢指针slow和快指针fast，其初始都指向链表头节点

然后，让快指针fast先向前移动K步,这里我们令K=2:

接着，慢指针slow和快指针fast同时向前移动，每次移动一步，直到快指针fast指向链表的尾节点。这里，快指针fast指向链表的尾节点，不再继续向后移动的原因是，我们需要将尾节点和链表头节点相连，因此其所指节点不能为nullptr。

此时，慢指针slow所指节点的下一个节点就是倒数第K个节点。

接着，要做的就是将快指针fast所指的尾节点的后继指针指向链表头节点，使链表成环。然后，倒数第K个节点作为链表旋转后的新的头节点，指针slow所指节点作为新的尾节点。

三、代码

class Solution {
public:
	ListNode* rotateRight(ListNode* head, int k) {
		if (head == nullptr) {
			return head;
		}

		// 计算链表中节点个数
		int len = calculateLen(head);
                // 链表首尾相连成环形链表，所以当k大于链表长度len时，对于一个节点来说其移动k个位置和移动k对len取余个位置结果是一样的。
		k = k % len; 

		// 慢指针初始指向头节点
		ListNode* slow = head;
		// 快指针初始指向头节点
		ListNode* fast = head;

		// 快指针先向前移动k步
		for (int i = 0; i < k; i++) {
			fast = fast->next;
		}

		// 快慢指针同时向前移动，直到快指针指向的节点的
		// 下一个节点为null
		while (fast->next != nullptr) {
			fast = fast->next;
			slow = slow->next;
		}

		// 快指针此时在链表末尾
		// 然后其指向的节点的后继指针指向头节点
		// 这时链表首尾相连成环
		fast->next = head;
		// 新的头节点是慢指针所指节点的下一个节点
		head = slow->next;
		// 慢指针所指节点的的后继指针指向nullptr
		// 断开环
		slow->next = nullptr;
		return head;
	}

	int calculateLen(ListNode* head) { // 计算链表长度
		int len = 0;
		while (head != nullptr) {
			head = head->next;
			len++;
		}
		return len;
	}
};

参考：

https://leetcode-cn.com/problems/rotate-list/solution/dong-hua-yan-shi-kuai-man-zhi-zhen-61-xu-7bp0/