61. 旋转链表

1. 题目

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

示例 1：

img

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

示例 2：

img

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

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9

2. 思路

  • 已知题目要求旋转链表，因此需要获取链表的长度，并将k对链表长度进行取余，取余的目的是为了避免无效旋转
  • 计算出取余后的k后，判断k是否为0，如果为0则表示无需旋转，直接返回结果head
  • 初始化链表头节点指针dummy，主要是为了有一个固定的头节点，在结果返回时，将返回dummy.next作为结果链表的头节点，默认的dummy.next值为当前链表的头节点
  • 旋转链表需要获取三个节点的对象，如下所示，分别需要获取rotatePreNode，rotateStartNode和rotateEndNode

image-20231004224708305

  • 获取以上三个节点后，将rotatePreNode的下一个节点置为空，因为该节点将在旋转后成为尾节点
  • 将rotateEndNode.next指向dummy.next即原始的头节点
  • 将dummy.next节点指向rotateStartNode ，即变更新的头节点
  • 返回dummy.next作为结果

3. 代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * 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 (head == null) {
            return head;
        }

        var length = len(head);
        k = k % length;

        if (k == 0) {
            return head;
        }

        var dummy = new ListNode();
        dummy.next = head;

        
        var rotatePreNode = get(dummy, length - k);
        var rotateStartNode = get(dummy, length - k + 1);
        var rotateEndNode = get(dummy, length);

        rotatePreNode.next = null;
        rotateEndNode.next = dummy.next;
        dummy.next = rotateStartNode;

        return dummy.next;
    }

    private ListNode get(ListNode head, int index) {
        for (var i = 0; i < index; ++i) {
            head = head.next;
        }
        return head;
    }

    private int len(ListNode head) {
        var count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        return count;
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

image-20231004223858341