长大后想做什么？做回小孩！

0%

LeetCode——旋转链表&旋转数组

发表于 分类于 Valine：
本文字数： 387

NO.61 旋转链表 中等 、NO.189 旋转数组 简单

NO.61 旋转链表 中等

3zzHQ1.png

思路一：成环再断 先将链表首尾相连形成环，然后找到旋转后的新链表的新头节点和尾节点，从两者之间断开形成需要的结果。

8prla4.png

8prurT.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ListNode rotateRight(ListNode head, int k) {
    if(head==null||head.next==null)return head;
    //标记初始链表的结尾，n记录节点数
    ListNode oldTail=head;
    int n=1;
    while (oldTail.next!=null){
        oldTail=oldTail.next;
        n++;
    }
    //链表成环
    oldTail.next=head;
    //旋转之后的新结尾
    ListNode newTail=head;
    for (int i = 1; i < n - k % n; i++) {
        newTail=newTail.next;
    }
    //新头节点
    ListNode newHead=newTail.next;
    //新尾节点和新头节点之间断开
    newTail.next=null;
    return newHead;
}

时间复杂度：O(n)

NO.189 旋转数组 简单

YbHmiq.png

思路一：环形替代 数组不需要像链表一样用一个循环去统计元素个数，但是数组也不方便像链表一样轻松直观地形成环。数组更像是一个一个的座位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
这道题就像换座位一样，假设有 5 个座位 [0,1,2,3,4] ，
座位上每个人 [A,B,C,D,E] 需要向后移动 3 个"座位"，到达最后的"角落"就循环到开头继续后移。
        0 号座位的人站 A 起来，把 3 号座位的人 D 赶到"一旁站着"，然后自己坐下完成移位；

        D 不甘心站在一边，就去找 1 号座位的人 B 并用同样的方法赶走 B，自己坐下完成移位；

        B 也不愿站着，就去赶走 4 号座位的人 E ，自己坐下完成移位；

        E 去赶走了 C ， 自己坐下完成移位；

        最后 C 一看，0 号座位没人坐，刚好适合自己，于是坐下，完成移位；

        至此，所有人完成换位，共换位 5 次。

但是有特殊情况：只有四个座位 [0,1,2,3] 分别坐着 [A,B,C,D] 需要没人后移 2 个座位，

        还是从 start=0 号座位开始，先是 A 去赶走 C，坐下完成移位；

        这时 C 一看刚好自己需要的位置 0 号座位是空的，直接坐下；

        此时没有人站在一旁，但是仅仅只进行了 2 次换位，于是去催促 start+1=1 号座位的人继续换位；

        B 去赶走了 D 坐在 3 号座位，D 去坐在空着的 2 号座位，完成移位；

        至此共换位 4 次，换位完成。

需要统计换位的总次数 count，需要记录本轮换位的开始位置 start，本轮当前需要进行换位的元素 pre 和 元素原本的位置 curr。

每轮换位的完成条件是需要换位元素的原本位置 == 开始位置start，此时如果没有全不完成换位，则从 start+1 的位置开始下一轮换位，直至所有元素都完成换位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public void rotate(int[] nums, int k) {
    int len = nums.length;
    k = k % len;
    //记录换位次数
    int count = 0;
    //从哪个位置开始换位
    int start = 0;
    while (count < len) {
        //本轮从哪个位置开始换位
        int curr = start;
        //需要换位的元素
        int pre = nums[curr];
        //开始本轮换位
        do {
            //要去抢占的位置
            int next = (curr + k) % len;
            //被赶走的元素
            int temp = nums[next];
            //pre 坐下
            nums[next] = pre;
            //下一个需要换位的元素 和 元素原本的位置
            pre = temp;
            curr = next;
            count++;
        } while (start != curr);
        start++;
    }
}

时间复杂度：O(n) 每个元素换位一次

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github