题目

难度：★★★☆☆
类型：链表
方法：构造环形链表

传送门

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例

示例 1

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL

解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL

解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

解答

我们可以首先把链表闭合成为环形链表，然后确定链表的断开位置，最后在该位置断开环形链表即可。需要注意的是，链表断开位置的确定是需要认真考虑的，这个位置与输入k有关，也与链表长度有关，所以需要在构造环形链表的同时统计链表的长度。

def create_linked_list(nums):
    """
    创建链表
    :param nums: 输入代表里链表的数字列表
    :return: 返回创建好的链表的头结点，可以得到整个链表的所有信息
    """
    if not nums:                        # 输入空列表
        return
    head = prev = ListNode(nums[0])     # 第一个结点
    for num in nums[1:]:
        tmp = ListNode(num)             # 创建当前结点
        prev.next = tmp                 # 挂在已经创建好的链表末尾
        prev = prev.next                # 指针后移
    return head


def print_linked_list(head):
    """
    打印链表
    :param head: 要打印的链表的头结点
    :return: 结点值列表
    """
    cur = head                              # 为了不改变输入，使用临时变量
    nums = []                               # 结果数组
    nodes = []
    circle_flag = False                     # 是否为环形链表的flag
    circle_nums = []                        # 环形区域的结果
    while cur:

        nodes.append(cur)
        if circle_flag:
            circle_nums.append(cur.val)     # 添加环形区域的元素
        else:
            nums.append(cur.val)

        cur = cur.next
        if cur in nodes:
            if nodes.count(cur) == 2:        # 第二次进入环形区
                break
            else:                           # 首次进入环形区，修改环形flag
                circle_flag = True

    if circle_flag:
        print("当前链表是环形链表")
        print("链表中的元素为：{}".format(nums))
        print("环形区的元素为：{}".format(circle_nums))
        print("入口元素为：{}".format(nums[len(nums)-len(circle_nums)]))
    else:
        print("链表中的元素为：{}".format(nums))
    return nums

class Solution:
    def rotateRight(self, head, k: int):
        # 考虑特殊情况
        if not head:
            return None
        if not head.next:
            return head

        # 寻找链表尾，并闭合成环形链表，同时计算链表长度
        tail = head
        num = 1
        while tail.next:
            tail = tail.next
            num += 1
        tail.next = head

        # 寻找需要断开的位置，新的尾结点：(n - k % n - 1)，新的头结点：(n - k % n)
        new_tail = head
        for _ in range(num - k % num - 1):
            new_tail = new_tail.next                    # 头部后移
        new_head = new_tail.next

        # 在所找到的位置断开环形链表
        new_tail.next = None
        return new_head


if __name__ == "__main__":
    s = Solution()
    a = create_linked_list([1, 2, 3, 4, 5])
    res = s.rotateRight(a, 1)
    print_linked_list(res)

如有疑问或建议，欢迎评论区留言~