题目描述
给定一个链表，将其向右旋转 k 个节点，其中 k 为非负整数。
示例
输入：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。
辅助工具类
为了方便测试和打印链表结构，我们定义以下公共节点类。
package common;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
static public ListNode listNodeWithIntArray(int[] input) {
ListNode head = new ListNode(0);
ListNode node = head;
for (int i : input) {
ListNode newNode = new ListNode(i);
node.next = newNode;
node = node.next;
}
return head.next;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
ListNode node = this;
while (node != null) {
sb.append(node.val).append("-->");
node = node.next;
}
return sb.append("Null").toString();
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
return false;
}
}
思路一：双指针配合长度计算
由于 k 可能比链表长度大，直接旋转会导致无效操作。我们需要先获取链表长度，然后计算实际需要移动的步数。
基本逻辑是：
- 遍历链表得到长度
len。 - 有效移动步数为
k % len。 - 找到第
len - (k % len)个节点作为新链表的尾部。 - 将原尾部连接到原头部形成环，再断开新尾部。
下面代码中使用了哑节点（dummy node）来简化边界处理，同时利用快慢指针定位断点。
public class RotateList {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
int len = 0;
// 获取链表长度
for (; fast.next != null; len++) {
fast = fast.next;
}
// 确定需要移动的步数
int step = len - k % len;
for (int s = 0; s < step; s++) {
slow = slow.next;
}
// 执行旋转：连成环后断开
fast.next = dummy.next;
dummy.next = slow.next;
slow.next = null;
return dummy.next;
}
public static void main(String[] args) {
RotateList obj = new RotateList();
int[] input = {1, 2, 3, 4, 5};
ListNode initNode = ListNode.listNodeWithIntArray(input);
System.out.println(initNode.toString());
ListNode resultNode = obj.rotateRight(initNode, 2);
System.out.println(resultNode.toString());
}
}
这里的关键在于理解 fast 最终指向的是原链表的尾节点，而 slow 指向的是新链表的尾节点。一旦 fast.next 指向了 dummy.next（即原头节点），整个链表就变成了一个环，此时只需将 slow.next 置空即可切断环，完成旋转。
思路二：显式构建环形链表
上述方法虽然可行，但逻辑上可以进一步简化。既然要旋转，不如直接把链表首尾相接变成一个环。
- 遍历链表找到尾节点并计算长度。
- 将尾节点的
next指向头节点。 - 计算新的断点位置：
len - k % len。 - 从当前尾节点向后移动该步数，此时的节点即为新的尾节点。
- 更新头节点为新尾节点的下一个节点，并将新尾节点的
next置空。
这种方法不需要额外的哑节点，内存占用更优，逻辑也更直观。
public class RotateList {
public ListNode rotateRightWithCircle(ListNode head, int k) {
if (head == null || head.next == null || k == 0) {
return head;
}
ListNode tail = head;
int len = 1;
// 计算长度并找到尾节点
while (tail.next != null) {
tail = tail.next;
len++;
}
// 形成环
tail.next = head;
// 找到新的尾节点位置
int step = len - k % len;
while (step > 0) {
tail = tail.next;
step--;
}
// 断开环，返回新头
head = tail.next;
tail.next = null;
return head;
}
public static void main(String[] args) {
RotateList obj = new RotateList();
int[] input = {1, 2, 3, 4, 5};
ListNode initNode = ListNode.listNodeWithIntArray(input);
System.out.println(initNode.toString());
ListNode resultNode = obj.rotateRightWithCircle(initNode, 2);
System.out.println(resultNode.toString());
}
}
运行结果
控制台输出如下，可以看到链表确实完成了预期的旋转：
1-->2-->3-->4-->5-->Null
4-->5-->1-->2-->3-->Null
总结来说，处理链表旋转问题，关键在于识别出'旋转'本质上就是'断点移动'。通过取模处理大数 k，以及利用环形结构简化指针操作，可以在 O(n) 时间和 O(1) 空间内高效解决问题。
