package com.example.medium;

public class RotateRight {

    private class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

        //思路2
    private ListNode rotateRight2(ListNode head, int k) {
        if(k < 0)return head;
           int length = 0;
        ListNode p = head;
            while(p != null){
                p = p.next;
                length++;
            }
            if(k >= length && length != 0)k = k%length;
            if(k == 0 || length == 0)return head;
            int values[] = new int[length];//定义一个数组，从数组的第k个位置开始复制链表的值
            p = head;
            while(p != null){//复制链表元素到数组
                values[k++] = p.val;
                if(k >= length)k = 0;//k超过数组尾部时，从零开始
                p = p.next;
            }
            p = head;
            k = 0;
            while(p != null){//再将数组的值复制回链表
                p.val = values[k++];
                p = p.next;
            }
        return head;
    }

        //思路1
    private ListNode rotateRight(ListNode head, int k) {
            //int values[] = new int[k];
            if(k < 0)return head;
            int length = 0;
            ListNode p = head;
            while(p != null){//求链表长度
                p = p.next;
                length++;
            }
            p = head;
            if(k >= length && length != 0)k = k%length;//求模去掉多余长度
            if(k == 0)return head;
            for(int i = 0;i < k && p != null;i++)p = p.next;//找到k的位置
            if(p == null)return head;//k > head.length
            ListNode q = head;
            while(p.next != null){//逆置链表
                p = p.next;
                q = q.next;
            }
            p.next = head;
            head = q.next;
            q.next = null;
            return head;
    }
    
    public void display(){
            int n = 5;
            ListNode head = null;
            for(int i = n;i > 0;i--){
                ListNode p = new ListNode(i);
                p.next = head;
                head = p;
            }
            ListNode p = head;
            while(p != null){
                System.out.println(p.val);
                p = p.next;
            }
            p = rotateRight2(head,7);
    }

    public static void main(String args[]){
        new RotateRight().display();
    }
}