题目信息
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
rotate1.jpg
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
解题思路
- 暴力破解：每次移动尾部节点到头部，移动k次。时间复杂度O(k*n)，空间复杂度O(1)
- 无效操作分析：
- 列表只有连接关系，没有index，因此必需要遍历一遍数组才能得知列表长度n
- 只需要移动 n - k % n 次即可，n的倍数次移动等于回到头部原点
- 优化方法：列表组环后再断开
- 考虑边界：
- 列表为null，不存在
- 列表只有一个元素，即head.next = null
- k为0
- 编码实现：时间复杂度O(n)，空间复杂度O(1)
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (k == 0 || head == null || head.next == null) {
return head;
}
int n = 1;
ListNode iter = head;
// 遍历求n
while(iter.next != null) {
iter = iter.next;
n++;
}
// 计算偏移
int offset = n - k % n;
if (offset == 0) {
return head;
}
// 组环
iter.next = head;
while (offset > 0) {
iter = iter.next;
offset--;
}
// 断开环，返回链表
ListNode ret = iter.next;
iter.next = null;
return ret;
}
}
题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/rotate-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
