题目

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

解题思路

1. 计算链表长度：遍历链表来获取链表的长度 n，因为链表的旋转其实是循环移动，所以将 k 对 n 取模 k = k % n，这样可以减少不必要的旋转次数。

2. 判断边界情况：如果 k 为 0 或 n 小于等于 1，则无需旋转，直接返回原链表。

3. 找到新链表的尾节点：旋转后的链表可以看作是从倒数第 k 个节点断开，将链表末尾连接到头部形成一个环，再在新的断点处截断形成新的链表。

   • 找到新链表的尾节点，即原链表的第 n - k 个节点，将它的 next 指向 null。

4. 返回新链表头节点：此时新链表的头节点是第 n - k + 1 个节点。

这样通过一次遍历获取长度，再一次遍历找到断点，时间复杂度为 O(n)。

代码

func rotateRight(head *ListNode, k int) *ListNode {if head == nil || head.Next == nil || k == 0 {return head}n := 1tail := headfor tail.Next != nil {tail = tail.Nextlength++}k %= nif k == 0 {return head}tail.Next = headnewTail := headfor i := 0; i < n-k-1; i++ {newTail = newTail.Next}newHead := newTail.NextnewTail.Next = nilreturn newHead
}