给你一个链表的头节点 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
# 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 not head or not head.next:
return head
_head = head
total = 0
while _head:
total += 1
_head = _head.next
_k = k % total
if _k == 0:
return head
dummy = ListNode(next=head)
slow = fast = dummy
while fast.next:
if _k < 1:
slow = slow.next
fast = fast.next
_k -= 1
first = slow.next
slow.next = None # forth
second = fast
third = dummy.next
dummy.next = first
second.next = third
return dummy.next
时间复杂度O(n)
空间复杂度O(1)
看了一眼官解，发现是先连成环然后再断开，比上面的思路时间复杂度常数更小，Python 实现如下
# 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 not head or not head.next:
return head
_head = head
total = 1
while _head.next:
total += 1
_head = _head.next
_head.next = head
count = total - k % total
while count:
_head = _head.next
count -= 1
res = _head.next
_head.next = None
return res
时间复杂度O(n)
空间复杂度O(1)
