import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
       // write code here
        //特殊值处理，当链表为空或者链表的长度为1时，链表是为回文结构
//         if(head == null || head.next == null){
//             return true;
//         }
//         int count = 0;  //计数器，统计链表的长度
//         ListNode head0 = head;
//         while (head0 != null){
//             count++;
//             head0 = head0.next;
//         }
//         head0 = head;
//         int k = count/2;  //链表对半分割
//         ListNode right = FindKthToTail(head0,k);  //查找链表的倒数第k个节点，并返回该节点的指针
//         right = ReverseList(right);  //反转链表
//         //经过链表对半分割，有链表反转后，将左链表和有链表逐一比较，如果存在节点值不相等，则不是回文结构
//         while (head0 != null && right != null){
//             if(head0.val != right.val){
//                 return false;
//             }
//             head0 = head0.next;  //左链表节点移动
//             right = right.next;  //右链表节点移动
//         }
//         //直到遍历链表结束，如果没有存在节点值不相等，则是回文结构，返回true
//         return true;
        
        //方法二：利用辅助数组，将链表的值转移到数组中，再进行比较，时间大概需要：250ms
        //特殊值处理，当链表为空或者链表的长度为1时，链表是为回文结构
        if(head == null || head.next == null){
            return true;
        }
        int count = 0;  //计数器，统计链表的长度
        ListNode head0 = head;
        while (head0 != null){
            count++;
            head0 = head0.next;
        }
        head0 = head;
        int[] arr = new int[count];  //创建一个长度为链表长度的整型数组
        int index = 0;
        while (head0 != null){//遍历链表，将链表中的值复制到整型数组中
            arr[index] = head0.val;
            index++;
            head0 = head0.next;
        }
        int size = count/2;
        for(int i=0;i<size;i++){//对数组中的值前后比较，如果存在值不相等，则不是回文结构
            if(arr[i] != arr[count-1-i]){
                return false;
            }
        }
        //直到遍历数组结束，如果没有存在值不相等，则是回文结构，返回true
        return true;
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 题目描述：输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
     *          如果该链表长度小于k，请返回一个长度为 0 的链表。
     *          eg：1->2->3->4->5->null（2）  {4，5}
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public static ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        //方法一：遍历链表，时间大概需要：260ms
        //特殊值处理，空链表
//        if(pHead == null){
//            return null;
//        }
//        int size = 0;  //计数器，统计链表的节点个数
//        ListNode head0 = pHead;
//        while (head0 != null){//统计链表的节点个数
//            size++;
//            head0 = head0.next;
//        }
//        head0 = pHead;
//        //特殊值处理，当链表长度小于k时，返回一个长度为 0 的链表
//        if(k > size){
//            return null;
//        }
//        //遍历链表，查找倒数第k个节点
//        while (size > k){
//            head0 = head0.next;  //节点移动
//            size--;
//        }
//        return head0;  //返回倒数第k个节点

        //方法二：利用快慢指针，时间大概需要：250ms
        ListNode fast = pHead;  //创建一个快指针
        //当快指针不为空。且k>0时，快指针移动
        while (fast != null && k > 0){
            fast = fast.next;
            k--;
        }
        //当快指针为空时，代表：链表长度小于k，请返回一个长度为 0 的链表
        if(fast == null && k > 0){
            return null;
        }
        ListNode flow = pHead;  //创建一个慢指针,指向链表的头节点
        //遍历链表，直到快指针指向空指针，此时慢指针指向倒数第k个节点
        while (fast != null){
            fast = fast.next;  //快指针移动
            flow = flow.next;  //慢指针移动
        }
        return flow;
    }
    
    /**
     * 题目描述：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，
     *          长度为n，反转该链表后，返回新链表的表头。ed:1->2->3,反转后：3->2->1
     *          数据范围： 0≤n≤1000，要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
     * @param head  链表的头指针
     * @return  ListNode 链表反转后的头指针
     */
    public static ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null){//特殊值处理，空链表，或者链表的长度为1
            return head;
        }
        ListNode prep = null;  //保存当前节点的前驱节点
        ListNode next = head.next;  //保存当前节点的后继节点
        while (head != null){//遍历链表，head指向当前遍历的链表节点
            next = head.next;  //保存当前节点的后继节点
            head.next = prep;  //实现链表方向反转
            prep = head;  //前驱节点后移
            head = next;  //当前节点后移
        }
        return prep;//返回链表反转后的头指针
    }
}