旋转链表

难度: Medium

给你一个链表的头节点 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⁹

Submission

运行时间: 52 ms

内存: 15 MB

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None:
            return None
        p = head
        length = 1
        while p.next:
            length += 1
            p = p.next
        p.next = head
        step = length - k % length - 1
        p = head
        for _ in range(step):
            p = p.next
        new_head = p.next
        p.next = None
        return new_head

Explain

该题解的思路是先遍历一遍链表，得到链表的长度length。然后将链表首尾相连成环，再计算出需要移动的实际步数 step = length - k % length - 1。最后再遍历 step 步，将环断开，得到旋转后的链表。

时间复杂度: O(n)

空间复杂度: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None:
            return None
        
        # 遍历链表，得到链表长度
        p = head
        length = 1
        while p.next:
            length += 1
            p = p.next
        
        # 将链表首尾相连成环
        p.next = head
        
        # 计算实际需要移动的步数
        step = length - k % length - 1
        
        # 遍历 step 步，将环断开
        p = head
        for _ in range(step):
            p = p.next
        new_head = p.next
        p.next = None
        
        return new_head

Explore

在这个算法中，如果链表长度为0（即链表为空），在函数的开始就有一个检查 `if head is None`，此时会直接返回 `None`，因此算法能够正确处理链表为空的情况。对于链表长度为1的情况，由于链表首尾相连后仍是同一个节点，并且 `k % length` 为0，因此任何旋转都不会改变链表的结构，算法也能正确处理这种情况。

算法通过取模操作 `k % length` 来处理这种情况。无论k的值有多大，`k % length` 的结果总是在0到length-1之间，这意味着算法只会进行必要的旋转步数，从而避免了无用的循环。这保证了算法的效率，即使k的值远大于链表长度。

使用 `length - k % length - 1` 的原因是算法实际上是在寻找新的尾节点。`k % length` 给出的是从头部开始的偏移量，但我们需要找到新链表的尾节点位置，然后将其指向 `None` 来断开环。计算 `length - k % length` 给出的是新的尾节点位置，减1则是因为我们需要从头节点开始计算。

在算法中，通过精确计算要移动的步数 `step` 并遵循这一步数来移动到正确的节点，然后断开这个节点的下一个连接来确保正确断开环。由于 `step` 是基于链表长度和k的计算得到的，这保证了旋转后的链表首尾相连的正确性和完整性。通过准确遵循计算得到的步数，我们可以确保不会发生链表的破坏或错误连接。