【每日打卡】2021-12-06 第27天 about leetcoderank HOT 18 OPEN

public boolean hasCycle(ListNode head) {
        /*
         常规思路：一直遍历链表，一边用map存储节点，一边检查 时间复杂度ON 空间复杂度 ON
         优化思路：如果链表有环，那么可以看做原型赛道，两个人围着操场跑步，跑得快的人终究会有一刻会拉开跑得慢的人一圈 此时快慢相遇
         快慢双指针思路难点在于 很容易空指针 时间复杂度O1:空间复杂度 ON
         */
        //特判 没有节点或者只有一个节点视为没有环
        if (head == null || head.next == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

 //删除排好序的链表里面的重复元素，只留下重复元素的一个
    public ListNode deleteDuplicates(ListNode head) {
        /*
         这里之所有哑巴节点直接指向head 而不是自己构造的节点 是因为有重复的元素也会保留一个，所以我保留head是一定可以的
         当然构造一个哑巴节点也可以 只不过返回时是dummy.next
         最开始我的写法没有else  每次删除之后便将指针后移，但是在遇到了1，1，1例子时预期是1我输出了1，1
         分析后发现 如果删除之后便将指针后移 而如果移动后指向的还是重复元素，便会漏删除，当然这可以在移动的时候继续判断
         但是循环体不就是在判断吗 
         错误写法：
          while (head != null && head.next != null){
            //保留当cur == next 删除next
            if (head.val == head.next.val){
                head.next = head.next.next;
            }
                head = head.next;
            
        }
        时间复杂度:因为要遍历所有的元素 所以时间复杂度是O(N)
        空间复杂度：O(1)
         */
        ListNode dummy = head;
        while (head != null && head.next != null){
            //保留当cur == next 删除next
            if (head.val == head.next.val){
                head.next = head.next.next;
            }else{
                head = head.next;
            }
        }
        return dummy;
    }

// 1 2 3 4
    // 1 2 3
    public boolean isPalindrome(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        //此种写法会导致slow节点永远停留在mid的前一个 见仁见智
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        mid = reverse(mid);
        //假如链表长度是奇数 其实切开后两端链表不是一样的长 比如 1，2，1 切开= 1，2 和 1 但是他仍然是回文链表
        //也就是说 存在一种情况 比较完毕之后 返回结果是true 所以内部的比较逻辑就是 ！=
        while (mid != null){
            if (head.val == mid.val){
                return false;
            }
            head = head.next;
            mid = mid.next;
        }
        return true;
    }

    private ListNode reverse(ListNode mid) {
        ListNode pre = null;
        while (mid != null){
            ListNode n = mid.next;
            mid.next = pre;
            pre = mid;
            mid = n;
        }
        return pre;
    }