题目描述

给定一个链表,旋转链表,将链表每个节点向右移动 个位置,其中 是非负数。

示例 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”为例。

图1 移动一个节点的过程

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

图2 最后一步,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的 ③ )。下图描述了该过程。

图3 解法2的过程

现在还有个问题,如何找到“切点”?我们以上图当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;
    }
}
pwrliang Algorithms, LinkedList

Leave a Reply

Your email address will not be published. Required fields are marked *