写一份链表顺序移动

假设有一个链表如下：

1 -> 2 -> 3 -> 4 -> 5

现在要将链表向右移动 k 个位置，即将最后 k 个节点移到链表头部，例如 k=2 时，移动后的链表为：

4 -> 5 -> 1 -> 2 -> 3

实现链表顺序移动的思路如下：

先遍历一遍链表，找到链表的尾部节点，并记录链表的长度 len。
对 k 进行取模运算，以防 k 大于链表长度 len。
如果 k 等于 0，则链表无需移动，直接返回原链表即可。
定义两个指针，分别指向链表头部和链表尾部。
将尾部节点的 next 指针指向头部节点，形成一个环形链表。
将头部指针向后移动 len-k-1 个位置，即找到新的头部节点。
将新的头部节点赋值给新的头部指针，并将尾部节点的 next 指针置为 null，打破环形链表。
返回新的头部指针，即为移动后的链表头部。

代码实现如下：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:
            return head
        
        # 遍历一遍链表，找到链表的尾部节点，并记录链表的长度 len
        p = head
        len = 1
        while p.next:
            p = p.next
            len += 1
        
        # 对 k 进行取模运算，以防 k 大于链表长度 len
        k %= len
        
        if k == 0:
            return head
        
        # 定义两个指针，分别指向链表头部和链表尾部
        tail = head
        for i in range(len-1):
            tail = tail.next
        
        # 将尾部节点的 next 指针指向头部节点，形成一个环形链表
        tail.next = head
        
        # 将头部指针向后移动 len-k-1 个位置，即找到新的头部节点
        p = head
        for i in range(len-k-1):
            p = p.next
        
        # 将新的头部节点赋值给新的头部指针，并将尾部节点的 next 指针置为 null，打破环形链表
        new_head = p.next
        p.next = None
        
        return new_head

时间复杂度：O(n)，其中 n 是链表的长度，需要遍历一遍链表。

空间复杂度：O(1)，只需要常数级别的额外空间