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

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

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

	[2,0,1]

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

• 面对这道算法题目，二当家的再次陷入了沉思。
• 首先节点向右移动的位置 k 为0，我们什么都不需要做，直接返回原来的链表即可。
• 如果想要旋转链表，就必须知道链表的长度，所以我们先从头遍历一次链表，计算一下链表的长度，如果长度是0，同样我们什么都不需要做，也直接返回原来的链表即可。
• 在知道链表的长度 n 之后，我们就可以旋转链表了，但是节点向右移动位置 k 的值可能大于链表的长度 n ，这时候我们并不需要真移动 k 个位置，因为每移动 n 个位置，链表就会恢复原状，所以我们只需要移动 k % n 个位置，而如果这个值是0时，我们依然可以什么都不做直接返回原来的链表。
• 移动之后，链表的头和尾会发生变化，所以需要确定新的尾和头然后将他们断开，并且把旧的尾和头相连。

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn rotate_right(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        if k == 0 || head.is_none() {
            return head;
        }

        // 链表的长度
        let mut n = 0;
        let mut tail = &head;
        while let Some(node) = tail {
            n += 1;
            tail = &node.next;
        }
        let add = n - k % n;
        if add == n {
            return head;
        }

        // 寻找新尾
        let mut tail = &mut head;
        for _ in 1..add {
            tail = &mut tail.as_mut().unwrap().next;
        }
        // 新头和新尾断开
        let mut ans = tail.as_mut().unwrap().next.take();

        // 找到旧尾
        let mut tail = &mut ans;
        while tail.is_some() && tail.as_ref().unwrap().next.is_some() {
            tail = &mut tail.as_mut().unwrap().next;
        }

        // 旧尾和旧头相连
        tail.as_mut().unwrap().next = head;

        return ans
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if k == 0 || head == nil || head.Next == nil {
		return head
	}

	// 链表的长度
	n := 1
	tail := head
	for tail.Next != nil {
		tail = tail.Next
		n++
	}
	add := n - k%n
	if add == n {
		return head
	}

	// 成环
	tail.Next = head

	// 寻找新尾
	for add > 0 {
		tail = tail.Next
		add--
	}

	// 新头
	ans := tail.Next

	// 新尾和新头断开
	tail.Next = nil

	return ans
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (k == 0 || head == nullptr || head->next == nullptr) {
            return head;
        }

        // 链表的长度
        int n = 1;
        ListNode *tail = head;
        while (tail->next != nullptr) {
            tail = tail->next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }

        // 旧尾连旧头成环
        tail->next = head;

        // 寻找新尾
        while (add--) {
            tail = tail->next;
        }

        // 新头
        ListNode *ans = tail->next;

        // 新尾和新头断开
        tail->next = nullptr;

        return ans;
    }
};

# 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
        # 确定链表的长度
        n = 1
        tail = head
        while tail.next:
            tail = tail.next
            n += 1
        if (add := n - k % n) == n:
            return head
        # 旧尾连旧头成环
        tail.next = head
        # 寻找新尾
        while add:
            tail = tail.next
            add -= 1
        # 新头
        ans = tail.next
        # 新尾和新头断开
        tail.next = None
        return ans

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }

        // 链表的长度
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
            n++;
        }
        int add = n - k % n;
        if (add == n) {
            return head;
        }

        // 旧尾连旧头成环
        tail.next = head;

        // 寻找新尾
        while (add-- > 0) {
            tail = tail.next;
        }

        // 新头
        ListNode ans = tail.next;

        // 新尾和新头断开
        tail.next = null;

        return ans;
    }
}