//无头单向非循环链表
class Node {
    //实例成员没有初始化，默认值为对应的0值，引用类型默认为null，简单类型默认为0
    public int data;//数值域---0
    public Node next;//下一个节点的引用---null
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

    //1、反转链表
    //方法一：直接翻方向（最好掌握这个方法，因为在后面的“回文结构”中也用到了这个方法）
    public Node reverseList(Node head) {
        Node prev = null;//需要反转的节点的前驱
        Node cur = head;//需要反转的节点
        Node newHead = null;//反转后的单链表的头
    //遍历链表
        while(cur != null) {
            Node curNext = cur.next;//需要反转的节点的后继
            if(curNext == null) {
                newHead = cur;
            }
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return newHead;
    }
    //方法二：头插法（取原链表的节点，头插到新链表）（相对于直接翻方向容易理解一些）
    public Node reverseList1(Node head) {
        Node cur = head;//进行头插的节点
        Node newHead = null;
        while(cur != null) {
            Node curNext = cur.next;//进行头插的节点的后继
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        return newHead;
    }

    public Node middleNode(Node head) {
        Node slow = head;
        Node fast = head;
        //只要fast或者fast.next有一个为空，那么肯定走到尾了，注意别忘记加上fast.next!=null
        //注意不能写成fast.next != null && fast != null这样，因为fast走两步后可能为空了，再执行 
        //循环fast.next可能会导致空指针异常
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public Node FindKthToTail(Node head, int k) {
        //单链表不能为空
        if(head == null) {
            return null;
        }
        //先判断k的合法性
        //此处为了只需一次遍历单链表就能解决问题，同时也为了提高时间效率，没有加上k > size()这个 
        //条件，所以后面要注意空指针异常(第一个while循环做了处理)，size()实际上是我写的求单链表 
        //长度的方法，在此你只要将k > size()理解成"k > 单链表的长度"即可
        if(k <= 0) {
            System.out.println("k不合法！");
            return null;
        }
        Node slow = head;
        Node fast = head;
        //不能让它一直往后面走，可能会导致空指针异常
        while(k - 1 > 0) {
            //设置fast.next != null这个条件就是防止k大于单链表的长度
            if(fast.next != null) {
                fast = fast.next;
                k--;
            }else {
                System.out.println("没有这个节点！");
                return null;
            }
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public Node deleteDuplication(Node head) {
        Node cur = head;
        Node newHead = new Node(-1);//定义的虚拟节点
        Node tmp = newHead;
        while(cur != null) {
            //一定要加上cur.next != null这个条件，防止一直朝后走导致空指针异常(因为后面要判断 
            //cur.data == cur.next.data,涉及cur.next，所以要多想一下)
            if(cur.next != null && cur.data == cur.next.data) {
                while(cur.next != null && cur.data == cur.next.data) {
                    cur = cur.next;
                }
                cur = cur.next;//多走一步(因为要把重复的节点全部删除掉)
            }else {
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }
        tmp.next = null;//最后一定不要忘记了将尾结点的next置为空
        return newHead.next;
    }

    public boolean chkPalindrome(Node head) {
        //单链表为空，肯定不是回文结构
        if(this == null) {
            return false;
        }
        //只有头结点自己，肯定是回文结构
        if(head.next == null) {
            return true;
        }
        //1、找到单链表的中间节点
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2、开始反转单链表的后半部分   slow肯定在中间位置
        Node cur = slow.next;
        while(cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //slow是最后的节点了
        //3、开始一个从头走，一个从尾走
        while(slow != head) {
            if(slow.data != head.data) {
                return false;
            }
            //判断偶数的情况(一定要注意的是不能比较的是元素大小！！！)
            if(head.next == slow) {
                return true;
            }
            slow = slow.next;
            head = head.next;
        }
        return true;
    }

    public Node detectCycle(Node head) {
        Node fast = head;
        Node slow = head;
        //如果有环，必然不会存在null
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        //相遇后，即有环，此时使用两个引用，一个从头开始走，一个从相遇点（此时的slow和fast就在相 
        //遇点）开始走，当二者相遇的时候就是入口点
        slow = head;
        while(slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    public Node getIntersectionNode(Node headA, Node headB) {
        //1、求长度，走差值步
        int lenA = 0;
        int lenB = 0;
        Node pl = headA;
        Node ps = headB;
        while(pl != null) {
            lenA++;
            pl = pl.next;
        }
        while(ps != null) {
            lenB++;
            ps = ps.next;
        }
        //注意此时pl，ps位置不再是头了，需要人为设置
        pl = headA;
        ps = headB;
        //len要放到这个位置计算，最基本的都忘记了！！！
        int len = lenA - lenB;
        //保证pl里面放的是长链表，ps里面放的是短链表
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //长的链表走差步值
        for(int i = 0; i < len; i++) {
            pl = pl.next;
        }
        //2、ps和pl一定在同一个起跑线上
        //设置ps != pl这个条件就是为了相交的时候停下来
        //别忘了pl != null && ps !=null 这个条件,其实也可以省去，因为两链表剩下的节点一样长！
        while(ps != pl && pl != null && ps != null) {
            ps = ps.next;
            pl = pl.next;
        }
        //二者相等也可能是两条链表都为空了
        if(pl == ps && pl != null) {
            return pl;
        }
        return null;
    }

    public void removeAllKey(Node head, int key) {
        //单链表为空时
        if(head == null) {
            return;
        }
        //需要注意的是始终要保证prev是cur的前驱
        Node prev = head;
        Node cur = head.next;//代表要删除的节点
        while(cur != null) {
            if(cur.data == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后再判断首节点
        if(head.data == key) {
            head = head.next;
        }
    }