LeetCode61-旋转链表

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/rotate-list/

中文链接：https://leetcode-cn.com/problems/rotate-list/

题目详述

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

示例 1:

1
2
3
4
5
输入: 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:

1
2
3
4
5
6
7
输入: 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

题目详解

在解决链表问题前可以先画图模拟一下。本题实际上是 k 对链表长度取模后，把链表的最后 k 个结点按顺序搬到链表的头部形成一个新的链表后返回新链表的头结点。有几个小技巧如下：

  • 链表为空或链表长度为 1 或 k == 0，都可以直接返回。
  • k 对链表长度取模可以避免重复遍历。同样，取模后 k == 0 可以直接返回。
  • 得到尾结点后，可以先把尾结点链接到头结点。之后置新链表的尾结点的 next 为 null 即可。
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
29
30
31
32
33
public class LeetCode_00061 {

    public ListNode rotateRight(ListNode head, int k) {
        // 如果链表为空或链表长度为 1 或 k == 0，直接返回
        if (head == null || head.next == null || k == 0) {
            return head;
        }
        // 计算链表长度
        ListNode cur = head;
        int len = 1;
        while (cur.next != null) {
            ++len;
            cur = cur.next;
        }
        // 取模可以避免重复遍历
        k %= len;
        // 如果 k 是链表长度的整数倍，那么移动后的结果与原始链表相同
        if (k == 0) {
            return head;
        }
        // 将尾结点链接到头结点，再移动 cur 让它指向结果链表的尾结点
        cur.next = head;
        int loop = len - k;
        for (int i = 1; i <= loop; ++i) {
            cur = cur.next;
        }
        // cur.next 为新的头结点
        head = cur.next;
        // 置 cur.next 为 null
        cur.next = null;
        return head;
    }
}