旋转链表

题目信息

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

rotate1.jpg

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

解题思路

1. 暴力破解：每次移动尾部节点到头部，移动k次。时间复杂度O(k*n)，空间复杂度O(1)
2. 无效操作分析：
   1. 列表只有连接关系，没有index，因此必需要遍历一遍数组才能得知列表长度n
   2. 只需要移动 n - k % n 次即可，n的倍数次移动等于回到头部原点
3. 优化方法：列表组环后再断开
4. 考虑边界：
   1. 列表为null，不存在
   2. 列表只有一个元素，即head.next = null
   3. k为0
5. 编码实现：时间复杂度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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。