import java.util.HashMap;

//单向 不带头 非循环
public class SingleLinkedList {

    //节点
    static class Node{
        //成员变量
        int val;
        Node next;
        //构造方法
        public Node(int val){
            this.val = val;
        }
    }

    //定义一个头节点
    Node head ;
    //尾插法
    public void addLast(int data){
        //1.创建一个节点
        Node node = new Node(data);

        //2.判断
        if(head == null){
            head = node;
        }else{
            //遍历链表，创建一个搜索方法
            Node cur = searchNode(head);
            //cur为尾部节点
            cur.next = node;
        }
        usedSize++;
    }
    private Node searchNode(Node head){
        //为了不改变头节点的位置，创建一个临时引用
        Node tem = head;

        //通过遍历循环，尾部节点的next为null
        while(tem.next != null){
            //进入循环说明该节点还不是尾部节点
            //将tem赋值为下一节点，直到不满之条件
            tem  = tem.next;
        }
        //返回
        return tem;
    }

    //头插法
    public void addFirst(int data){
        //1.创建节点
        Node node = new Node(data);
        //2.判断
       if(head == null){
           head = node;
       }else{
           node.next = head;
           head = node;
       }
       usedSize++;
    }

    //节点数量
    int usedSize;//每次增加元素++
    //任意位置插⼊,第⼀个数据节点为0号下标
    public void addIndex(int index,int data){
        Node node = new Node(data);
        //1.判断是否为头插
        if(index == 0){
            addFirst(data);
            return;
        }
        //2.判断是否为尾插
        else if(index == usedSize){
            addLast(data);
            return;
        }
        //3.中间插入：找到插入位置的前一个元素
        Node prev = searchPrevNode(index);
        //node节点next赋值
        node.next = prev.next;
        //改变prev的next
        prev.next = node;
        usedSize++;

    }
    private Node searchPrevNode(int index){
        Node tem = head;
        //例如获取索引2节点的前一个节点
        //2  >  1 tem为索引1节点 1 > 1为假
        while(index  > 1){
            tem = tem.next;
            index--;
        }
        return tem;
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        //没有节点
        if(head == null) return false;
        //循环遍历
        Node tem  = head;
        while(tem != null){
            //满足返回真
            if(tem.val == key) return true;
            //遍历下一节点
            tem = tem.next;
        }
        //不满足条件
        return false;
    }

    //删除第⼀次出现关键字为key的节点
    public void remove(int key){
        if(head == null){
            System.out.println("没有值为" + key + "的节点");
            return;
        }
        //获取key节点
        Node ret = findNode(key);
        if(ret == null){
            System.out.println("没有值为" + key + "的节点");
            return;
        }

        //1.如果只有一个节点
        if(usedSize == 1){
            head = null;
            usedSize--;
            return;
        }
        //2.多个节点：删除头节点
        if(ret == head){
           head = head.next;
        }//删除尾节点
        else if(ret.next == null){
            //找到前一个节点
            Node prev = findPrev(ret);
            prev.next = null;
        }//删除中间节点
        else{
            //找到前一个节点
            Node prev = findPrev(ret);
            prev.next = ret.next;
        }
        usedSize--;
    }
    private Node findPrev(Node key){
        Node tem = head;
        while(tem != null){
            if(tem.next == key) {
                return tem;
            }
            tem = tem.next;
        }
        //找不到
        return null;
    }
    private Node findNode(int key){
        Node tem = head;
        while(tem != null){
            if(tem.val == key) {
                return tem;
            }
            tem = tem.next;
        }
        //找不到
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) return;
        Node tem = head;
        while(tem != null){
            if(tem.val == key){
                remove(key);
            }
            tem = tem.next;
        }
    }

    //得到单链表的⻓度
    public int size(){
        return usedSize;
    }

    //回收节点
    public void clear() {
        //如过val值是引用数据类型，需要将每一个赋值为null
        /*Node tem = head;
        while(tem != null){
            tem.val = null;
            tem = tem.next;
        }*/
        //最后间head赋值
          head = null;
    }

    //遍历单链表
    public void display() {
        Node tem = head;
        System.out.print("[");
        while(tem != null){
            System.out.print(tem.val + " ");
            tem = tem.next;
        }

        System.out.println("]");
    }

    //反转单链表
    public void reverseSingleLinkedList(Node head){
        //没有元素或者只有一个节点
        if(head == null || usedSize == 1) return;

        //由多个元素
        Node tem = head;
        Node cur = head.next;
        //满足条件说明cur前面还有节点
        while(cur != null){
            //cur下一给节点
            Node curNext = cur.next;
            cur.next = tem;
            tem = cur;
            cur = curNext;
        }
        //head的next赋值为null,并将head赋值
        head.next = null;
        head = tem;
    }
    //给定x值分割后合并
    public void partition(int x){
        Node h1 = null;
        Node h2 = null;
        int usedSize1 = 0;
        int usedSize2 = 0;

        Node tem = head;
        //遍历链表
        while(tem != null){
            //h1添加
            if(tem.val < x) {
                //首次添加
                if(h1 == null){
                    h1 = tem;
                }else{
                    //找到末尾节点后添加
                    Node last = searchLastNode(h1,usedSize1);
                    last.next = tem;
                }
                usedSize1++;
            }//h2添加
            else {
                //首次添加
                if (h2 == null) {
                    h2 = tem;
                } else {
                    Node last = searchLastNode(h2, usedSize2);
                    last.next = tem;
                }
                usedSize2++;
            }
            tem = tem.next;
        }

        //将h1 和 h2 合并：找到h1的尾部节点last，改变last.next = h2，
        Node last1 = searchLastNode(h1,usedSize1);
        last1.next = h2;
        //找到h2最后一个节点，将其next赋值为null
        Node last2 = searchLastNode(h2,usedSize2);
        last2.next = null;
    }
    private Node searchLastNode(Node head,int size){
        //为了不改变头节点的位置，创建一个临时引用
        Node tem = head;

        //通过遍历循环，尾部节点的next为null
        while(size > 1){
            //进入循环说明该节点还不是尾部节点
            //将tem赋值为下一节点，直到不满之条件
            tem  = tem.next;
            size--;
        }
        //返回
        return tem;
    }

    //获取中间节点
    public Node midNode(Node head){
        //判断是否没有节点或者只有一个节点
        if(head == null || head.next == null){
            return null;
        }

        //定义快慢双指针
        Node slow = head;
        Node fast = head;
        //不能改变判断条件的位置，否则如果fast为null，
        //判断fast.next会发生空引用异常
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public boolean palindrome(Node head){
        //1.获取中间位置
        Node mid = midNode(head);

        //2.逆序链表
        Node right = reverseSingleLinkedList1(mid);

        //3.判断是否回文
        Node left = head;
        while(left != null){
            //不相等直接返回
            if(left.val != right.val){
                return false;
            }//相等并且head.next == last返回true
            else if( left == right || left.next == right){
                return true;
            }
            left = left.next;
            right = right.next;
        }
        return false;
    }
    //反转单链表
    public Node reverseSingleLinkedList1(Node head){
        //没有元素或者只有一个节点
        if(head == null || usedSize == 1) return null;

        //由多个元素
        Node tem = head;
        Node cur = head.next;
        //满足条件说明cur前面还有节点
        while(cur != null){
            //cur下一给节点
            Node curNext = cur.next;
            cur.next = tem;
            tem = cur;
            cur = curNext;
        }
        head.next = null;
        return tem;
    }

    //查找入口点
    public Node detectCycle(Node head){

        //先判断是否存在环形结构
        if(!existtCycle()){
            return null;
        }

        //定义快慢双指针
        Node slow = head;
        Node fast = head;

        //走到相遇点
        while(fast != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }

        //此时fast是相遇点，将slow从新赋值
        slow = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }

        //相遇点
        return slow;
    }
    private boolean existtCycle(){
        Node slow = head;
        Node fast = head;

        while(fast != null && fast.next != null){
            if(fast == slow) return true;
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }
    public static Node createCycle(SingleLinkedList s){
        s.addLast(1);
        s.addLast(2);
        s.addLast(3);
        Node last1 = s.searchNode(s.head);
        s.addLast(2);
        s.addLast(1);
        Node last2 = s.searchNode(s.head);
        last2.next = last1;

        return s.head;
    }

}