大家好，我是 程序员小熊，来自某 大厂 的程序猿，今天带来一道来自互联网大厂（字节、腾讯、微软、苹果等） 面试题 Leetcode 61. 旋转链表 ，提供 虚拟头节点 + 双指针 的解题思路，采用 动图 的方式进行层层剖析，供大家参考，希望对大家无论是刷题还是面试都有所帮助。
描述
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
思考
考虑以下几种情况：
特殊情况
一般情况
思路
以链表 1->2->3->4->5，k = 2 为栗子，如下图所示。
增加虚拟头节点，设置两根快慢指针 fast/slow 指向它；
先让快指针 fast 向前移动 k 步，慢指针 slow 保持不动；
快慢指针 fast/slow 同时向前移动，直至快指针指向尾节点；
让快指针 fast 指向的节点指向链表的头节点；
将慢指针 slow 指向的节点的下一节点设置为新链表的头节点；
将慢指针 slow 指向的节点设置为新链表的尾节点 slow->next = null；
旋转原链表后得到新链表。
完整动图
反思
采用 双指针 中的 快慢指针 。
本题设置 虚拟头节点 的作用是找到 新链表的头节点和尾节点。通过 快慢指针 去寻找。
1 ListNode* rotateRight(ListNode* head, int k) {
2 /* 特殊情况判断 */
3 if (head == nullptr || head->next == nullptr || k == 0) {
4 return head;
5 }
6
7 /* 增加虚拟头节点 */
8 ListNode* dummy = new ListNode(0);
9 dummy->next = head;
10
11 /* 获取链表长度 */
12 int len = 0;
13 for (ListNode* node = head; node != nullptr; node = node->next) {
14 len++;
15 }
16
17 k %= len;
18 /* 判断 k 是否是 len 的整数倍 */
19 if (k == 0) {
20 return head;
21 }
22
23 /* 获取新链表的头尾节点 */
24 ListNode *fast = dummy, *slow = dummy;
25 for (int i = 0; i < k; ++i) {
26 fast = fast->next;
27 }
28 while (fast->next != nullptr) {
29 fast = fast->next;
30 slow = slow->next;
31 }
32 fast->next = head;
33 head = slow->next;
34 slow->next = nullptr;
35
36 /* 释放虚拟头节点 */
37 delete dummy;
38
39 return head;
40 }
1 ListNode rotateRight(ListNode head, int k) {
2 if (k == 0 || head == null || head.next == null) {
3 return head;
4 }
5
6 ListNode dummy = new ListNode(0);
7 dummy.next = head;
8
9 int len = 0;
10 for (ListNode node = head; node != null; node = node.next) {
11 len++;
12 }
13
14 k %= len;
15 if (k == 0) {
16 return head;
17 }
18
19 ListNode fast = dummy, slow = dummy;
20 for (int i = 0; i < k; ++i) {
21 fast = fast.next;
22 }
23 while (fast.next != null) {
24 fast = fast.next;
25 slow = slow.next;
26 }
27 fast.next = head;
28 head = slow.next;
29 slow.next = null;
30
31 return head;
32 }
关注公众号【程序员小熊】
