题目

题目描述

给你一个链表的头节点 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. 计算链表长度：首先遍历链表以获取其长度，并找到链表的尾节点。
2. 处理 k 值：如果 k 大于链表的长度，则实际需要旋转的位置为 k % 链表长度，因为旋转链表的周期性特性。
3. 形成环形链表：将尾节点指向头节点，形成一个环形链表。
4. 找到新的头节点和尾节点：根据实际需要旋转的位置，确定新的头节点和尾节点。
5. 断开环：将新的尾节点的 next 设置为 null，恢复链表结构。

Python 实现代码

def rotateRight(head: ListNode, k: int) -> ListNode:
    if not head or not head.next or k == 0:
        return head
    
    # 计算链表长度并找到尾节点
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1
    
    # 计算实际需要旋转的位置
    k %= length
    if k == 0:
        return head
    
    # 形成环形链表
    tail.next = head
    
    # 找到新的尾节点位置
    new_tail = head
    for _ in range(length - k - 1):
        new_tail = new_tail.next
    
    # 新的头节点
    new_head = new_tail.next
    
    # 断开环
    new_tail.next = None
    
    return new_head

代码解释

1. 计算链表长度：通过遍历链表来计算其长度，并找到尾节点。
2. 处理 k 值：使用 k % length 来确定实际需要旋转的位置，避免不必要的多次旋转。
3. 形成环形链表：将尾节点的 next 指向头节点，形成环形链表。
4. 找到新的头节点和尾节点：从头节点开始，向前移动 length - k - 1 步找到新的尾节点，其 next 即为新的头节点。
5. 断开环：将新的尾节点的 next 设置为 None，恢复链表结构。

这种方法的时间复杂度为 O(n)，其中 n 是链表的长度，因为我们只需要遍历链表几次。空间复杂度为 O(1)，因为我们只使用了常数级别的额外空间。

提交结果