文章目录：
- 题目要求
- 解题思路
- 具体实现
- 改进之路
- 总结
1. 题目要求
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 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
示例 3:
输入: 0->1->2->NULL, k = 3
输出: 0->1->2->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
来源：力扣LeetCode
本文仅做个人刷题记录，不做任何商业用途。
2. 解题思路
根据测试用例，可以知道：
a. 链表反转次数 和 k 与链表长度之间的关系 有关联；
b. 求链表长度 length；length == 0 或 length == k，链表不变；
c. 将链表每个节点向右移动 k 个位置，即 第 i 位置的元素 移到 第 i+k 位置 ，考虑到单链表的移动问题，将链表头尾相连转换成循环链表，
old_tail.next = old_head;
d. 找到新的表头（即 n-k ）和表尾( n-n%k-1 )， new_head = new_tail.next;
e.断开循环链表，恢复单链表，new_tail.next = null.
3. 具体实现
public ListNode rotateRight(ListNode head, int k) {
//界值判断
if(head==null||k==0){
return head;
}
//新建一个链表
ListNode res=head;
ListNode tail=null;
int length=1;
//获取链表长度，新链表赋值
while(res.next!=null)
{
res=res.next;
length++;
}
//得到循环的次数
int loop=length-(k%length);
//指向尾结点
tail=res;
//连接成循环链表
res.next=head;
res=head;
for(int i=0;i<loop;i++){
res=res.next;
tail=tail.next;
}
//断开
tail.next=null;
return res;
}
4. 改进之路
a. 先连接头和尾，形成环；
b. 找到新的尾结点和头结点；
c. 断开闭环。
public ListNode rotateRight(ListNode head, int k) {
// 界值判断
if (head == null) return null;
if (head.next == null) return head;
// 连接头和尾，形成闭环
ListNode old_tail = head;
int n;
for(n = 1; old_tail.next != null; n++){
old_tail = old_tail.next;
}
// 界值判断
if(n == k) return head;
old_tail.next = head;
// 新的尾结点 : 第 (n - k % n - 1)个结点
// 新的头结点 : 第 (n - k % n)个结点
ListNode new_tail = head;
for (int i = 0; i < n - k % n - 1; i++){
new_tail = new_tail.next;
}
ListNode new_head = new_tail.next;
//断开
new_tail.next = null;
return new_head;
}
5. 总结
先想清楚测试用例，确定边界和逻辑，然后根据测试用例写代码。文中内容参考了 leetcode 给出的标准答案。
