题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 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

https://leetcode-cn.com/problems/rotate-list/

解法1

题目要求移动链表的k个元素，我们不妨先考虑只移动一个元素的情况。对于除了最后一个节点外的每个节点，我们都做以下动作。

• 备份下一个节点的值
• 将上一个节点的值覆盖到下一个节点
• 下一个节点的值作为“新的上一个节点的值”
• 移动到下一个节点

如果遇到最后一个节点，则将该节点的值覆盖到第一个节点上。下面我们用图来描述以下过程，下图以“1->2->3->4->5->NULL”为例。

上面的图描述了移动一个节点后的结果，当p指向倒数第二个节点时循环终止，此时nextBak=5。循环结束后，我们用nextBak覆盖掉头节点的值就完成了移动一个节点的过程。

我们还可以做一个优化，这个优化很容易想到。当移动次数k超过链表长度n时，我们只需要移动n%k个位置即可。下面的代码实现了上述全部过程。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null)
            return null;

        ListNode p = head;
        int n = 0;
        
        // 计算链表长度
        while (p != null) {
            n++;
            p = p.next;
        }

        // 优化
        k = k % n;

        for (int i = 0; i < k; i++) {
            p = head;
            int lastBak = head.val;

            while (p.next != null) {
                int nextBak = p.next.val;
                p.next.val = lastBak;
                lastBak = nextBak;
                p = p.next;
            }

            head.val = lastBak;
        }

        return head;
    }
}

解法2

上面的算法如果使用了优化，最多要移动n-1次单个元素。而移动单个元素的代价是移动链表中所有的元素，也就是n。因此，解法1的时间复杂度为O(n^2)。我们能不能只移动一次，来降低时间复杂度呢？

我们通过计算找到链表的一个“切点”（图3的 ① ），然后将头节点指向切口的下一个节（图3的 ② ）点，最后将链表断开（图3的 ③ ）。下图描述了该过程。

现在还有个问题，如何找到“切点”？我们以上图当k=2时移动两个元素为例，切点应为第三个节点与第四个节点之间，也就是倒数第二个节点的前一个。我们可以总结出，从头节点出发遍历n-n%k-1个位置就能够找到“切点”。容易看出，该算法的时间复杂度为O(n)。全部代码如下所示。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null ||  k <= 0)
            return head;
        int n = 1;
        ListNode tail = head, p = head;

        while (tail.next != null) {
            n++;
            tail = tail.next;
        }

        k = n - k % n - 1; // 计算实际需要移动指针的次数

        for (int i = 0; i < k; i++)
            p = p.next;

        tail.next = head;
        ListNode newHead = p.next;
        p.next = null;

        return newHead;
    }
}