class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0) return head;
        ListNode sentry = new ListNode(0);
        sentry.next = head;

        int len = 0; // 求链表长度
        ListNode p = sentry;
        while (p.next != null) {
            len += 1;
            p = p.next;
        }

        if (len == 0) return null;
        k = k % len;
        if (k == 0) return head;

        // 找到旋转后的尾结点
        ListNode q = sentry;
        int m = 0;
        while (m < len - k) {
            m += 1;
            q = q.next;
        }
        ListNode newHead = q.next;
        q.next = null;

        // 找到旋转前的尾结点，将他连到旋转前的头结点上
        ListNode l = newHead;
        while (l.next != null) {
            l = l.next;
        }
        l.next = head;

        return newHead;
    }
}