61.旋转链表

题目:61.旋转链表

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

• 示例 1：

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

• 示例 2：

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

• 提示：

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

思路

1. 边界情况处理：

   • 首先检查链表是否为空或只有一个节点，或者 k 是否为 0。这些情况下，无需做任何处理，直接返回原链表。

2. 计算链表的长度：

   • 使用一个指针 current 遍历链表，计算链表的总长度 listSize。同时，通过遍历，找到链表的最后一个节点（尾节点）。

3. 将链表连接成环：

   • 由于旋转后链表的结构会有变动，可以将链表的尾节点指向头节点，形成一个循环链表。这样就不需要担心旋转操作后链表的结构改变。

4. 计算新的头节点位置：

   • 旋转 k 次相当于将链表的最后 k 个节点移到链表的开头。由于链表长度为 listSize，实际旋转次数等价于 k % listSize。
   • 计算新的头节点的位置，即从旧的头节点往后走 listSize - k 步的位置。

5. 断开循环链表，形成新链表：

   • 从原链表的尾节点开始遍历 listSize - k 步，找到新的头节点，将该节点之前的链表断开，形成新的链表结构。

6. 返回新的头节点：

   • 新的头节点即为旋转后的链表头部，返回它即可。

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

代码

public ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) {
        return head;
    }
    ListNode current = head;
    int listSize = 1;
    // 计算链表的长度
    while (current.next != null) {
        current = current.next;
        listSize++;
    }
    // 将链表连接成环
    current.next = head;
    // 计算新的头节点位置
    k = k % listSize;
    int step = listSize - k;
    // 找到新的头节点，并断开环
    for (int i = 0; i < step; i++) {
        current = current.next;
    }
    head = current.next;
    current.next = null;
    return head;
}