旋转链表问题（python3）

问题描述

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

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

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

解题思路

直接考虑链表的分离与合并，从给定的移动位置出发，找出分割结点的位置，断开链表，最后将分割出来的另一个链表的尾结点连接到原链表的头结点，完成链表的旋转。

代码实现

# 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 k == 0 or head is None:return headpre = head# 计算原链表长度numnum = 0while pre:num+=1pre = pre.next# 计算最终的移动距离# 如果移动距离大于长度，取余数if k>num:k = k%numprint(k)# 如果移动距离与长度一致，相对位置不变elif num == k:return headelse:k = k# 移动位置与长度成倍数时，相对位置也不变if k == 0:return head# 用于标记链表需要断开的结点位置flag = num - kcur_head = ListNode(-1)middle = headwhile middle:if flag == 1:# 记录断开的另一个链表头节点cur_head.next = middle.next# 将原链表断开位置指向空，表示该位置作为移动后的尾结点middle.next = Nonebreakmiddle = middle.nextflag -= 1# 记录新位置的headtemp = cur_head.nextwhile cur_head.next:cur_head = cur_head.next# 将断开后的另一个链表的尾部连接到原链表的头节点位置cur_head.next = headreturn temp