61.旋转链表.md

61. 旋转链表

https://leetcode-cn.com/problems/rotate-list/

难度：中等

题目：

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

提示：

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

示例：

示例 1：

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

输出：[4,5,1,2,3]

示例 2：

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

输出：[2,0,1]

分析

这道解题需要拆分成6个步骤完成：

1. 首先获取链表的长度
2. 针对K大于链表长度的情况进行求余，若k为0表示链表完成一次循环滚动，直接返回链表
3. 创建快慢指针，两者相距K，快指针先行K步，然后快慢指针一同向前滚动
4. 当结束滚动，慢指针的next即为新的头节点，fast指针在队尾
5. 此时将新节点指向slow.next,然后断开slow.next，再将fast指针指向原链表头部
6. 返回新的头节点，结束。

解题：

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        # 若链表为空，返回head
        if not head:
            return head
        # 获取链表的长度
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next
        # 若k的长度大于n，将k对n求余
        k = k % n
        # 若k==0表示循环了一整遍，直接返回head
        if k == 0:
            return head
        # 创建快慢指针
        slow = fast = head
        # fast指针先走k步
        while k:
            fast = fast.next
            k -= 1
        # 让fast指针走到队尾
        while fast.next:
            fast = fast.next
            slow = slow.next
        # 此时show.next为新的链表头
        new_head = slow.next
        # 断开slow.next
        slow.next = None
        # 链表首位相接
        fast.next = head
        # 返回新的链表头
        return new_head

欢迎关注我的公众号: 清风Python

我的个人博客：https://qingfengpython.cn