61.旋转链表.md

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 * 109

解题思路

1. 首先特殊情况（head为空或k=0）
2. 考虑k超出链表总长度的情况，为了不重复操作，先获取链表长度，再用k%length，获取小于length的k
3. 构造一个哑节点，next指向head
4. 双指针，fast、slow，指向哑节点
5. 移动fast length-k步
6. 移动slow到最后一个节点
7. 交换位置

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not k:
            return head

        # 1.计算链表长度
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        # 2.获取k%length
        k = k % length
        if k >= length:
            return head

        # 3.构造一个哑节点，指向head
        dummy_node = ListNode(0)
        dummy_node.next = head

        # 4.双指针
        fast = slow = dummy_node
        move_step = length - k
        for i in range(move_step):
            fast = fast.next

        # 5.移动slow到最后一个节点
        while slow.next:
            slow = slow.next

        slow.next = dummy_node.next
        dummy_node.next = fast.next
        fast.next = None

        return dummy_node.next