题目
难度：★★★☆☆
类型：链表
方法：构造环形链表
给定一个链表，旋转链表，将链表每个节点向右移动 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)
如有疑问或建议，欢迎评论区留言~
