📑 题目：61. 旋转链表

🚀 本题 LeetCode 传送门

题目大意

旋转链表 K 次。

解题思路

这道题需要注意的点是，K 可能很大，K = 2000000000 ，如果是循环肯定会超时。应该找出 O(n) 的复杂度的算法才行。由于是循环旋转，最终状态其实是确定的，利用链表的长度取余可以得到链表的最终旋转结果。

这道题也不能用递归，递归解法会超时。

代码

package leetcode
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
 if head == nil || head.Next == nil || k == 0 {
  return head
 }
 newHead := &ListNode{Val: 0, Next: head}
 len := 0
 cur := newHead
 for cur.Next != nil {
  len++
  cur = cur.Next
 }
 if (k % len) == 0 {
  return head
 }
 cur.Next = head
 cur = newHead
 for i := len - k%len; i > 0; i-- {
  cur = cur.Next
 }
 res := &ListNode{Val: 0, Next: cur.Next}
 cur.Next = nil
 return res.Next
}