week03_day03_环形链表&&反转链表

接昨天内容：

2. 判断链表中是否有环（同LeetCode之环形链表）
   时间复杂度和空间复杂度取决于最坏情况下的复杂度
   

package com.cskaoyan.exercise;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.Phaser;

/**
 * @author shihao
 * @create 2020-05-12 21:04
 * <p>
 * 判断链表中是否有环
 * 1. 给一个阈值（10ms）,如果在遍历链表的过程中10ms还没有结束，就认为有环。
 * 2. 迷雾森林
 *    Collection visited = new ArrayList();
 *    a.遍历链表，获取每一个结点。
 *      判断结点是否在visited集合中存在。
 *      存在：返回true
 *      不存在：将该结点添加到visited中，然后遍历下一个结点
 *    b.遍历结束后，返回false
 * 3. 跑道(快慢指针)
 *     a.创建了快指针和慢指针，快指针每次走两步，慢指针每次走一步
 *     b.遍历链表
 *       如果快指针到到终点：返回false
 *       如果快指针和慢指针相遇：返回true
 *       快指针移动两步
 *       慢指针移动一步
 */
public class Exercise02 {

    public static void main(String[] args) {

        Node head = new Node(0, null);
        Node n = new Node(11, head);

        for (int i = 1; i < 11; i++) {
            //新建一个结点
            Node node = new Node(i);

            //头插法
            node.next = head.next;
            head.next = node;

//            if (i == 10) {
//                node.next = n;
//            }
            //环 n---->head---->node---->n
        }

        System.out.println(hasCycle3(head));
    }

    //法一：哈希表
    //时间复杂度 o(n)    空间复杂度o(n)
    public static boolean hasCycle(Node head) {
        Set<Node> set = new HashSet<>();
        Node q = head;
        while (q != null) {
            if (set.contains(q)) {
                return true;
            } else {
                set.add(q);
                q = q.next;
            }
        }
        return false;
    }

    //法二：快慢指针
    //时间复杂度 o(n)  空间复杂度o(1)
    public static boolean hasCycle2(Node head) {
        if (head == null || head.next == null) {
            return false;
        }

        Node slow = head;
        Node fast = head.next;

        while (slow != fast) {
            //fast == null || fast.next == null  两个条件的顺序不能改，
            //短路原则，应该先判断fast是否为空，为空就不判断fast.next了
            //但如果先判断fast.next是否为空，如果fast就是null，哪来的fast.next呢？
            //此时就会报错  NullPointerException  空指针异常
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }

    //法三：老师的方法，其实就是把Set换成了Collection
    //时间复杂度o(n)   空间复杂度o(n^2)
    //为啥空间复杂度是o(n^2)?
    //每次从一个visited集合中找一个元素花费n，找n次，即o(n^2)
    //而HashSet每次从中找一个元素的开销为1，找n次，即o(n)
    public static boolean hasCycle3(Node head) {

        Collection visited = new ArrayList();
        Node q = head;
        while (q != null) {
            if (visited.contains(q)) {
                return true;
            } else {
                visited.add(q);
                q = q.next;
            }
        }
        return false;
    }

    //方法四：快慢指针法：老师方法
    public static boolean hasCycle4(Node head) {
        Node slow = head;
        Node fast = head;

        //因为刚开始slow就==fast，所以用do...while循环，先做再判断
        do {
            if (fast == null || fast.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        } while (slow != fast);

        return true;
    }
}

我们来分析快慢指针的时间复杂度：

判断链表有无环的问题就解决了。

接下来看升级版环形链表，（同LeetCode之环形链表II）：
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

package com.cskaoyan.exercise;

import java.util.HashSet;

/**
 * @author shihao
 * @create 2020-05-13 12:29
 * <p>
 * 如果有环：返回入环的第一个结点
 * 如果无环：返回null
 * 1. 迷雾森林
 * Collection visited = new ArrayList();
 * a.遍历链表，获取每一个结点。
 * 判断结点是否在visited集合中存在。
 * 存在：返回该节点
 * 不存在：将该结点添加到visited中，然后遍历下一个结点
 * b.遍历结束后，返回null
 * 2. 跑道(快慢指针)
 */
public class Exercise02_II {

    public static void main(String[] args) {
        // 1 --> 2 --> 3 --> 4
/*        Node head = new Node(4);
        head = new Node(3, head);
        head = new Node(2, head);
        head = new Node(1, head);
        System.out.println(detectCycle(head));*/

        // 1 --> 2 --> 3 --> 4 --> 2 --> ...
/*        Node node = new Node(4);
        Node head = new Node(3, node);
        head = new Node(2, head);
        node.next = head;
        head = new Node(1, head);
        System.out.println(detectCycle(head));*/

        // 1 --> 2 --> 3 --> 4 --> 4 --> ...
        Node node = new Node(4);
        node.next = node;
        Node head = new Node(3, node);
        head = new Node(2, head);
        head = new Node(1, head);
        System.out.println(detectCycle(head));
    }

    //法一：哈希表
    //时间复杂度：o(n)  空间复杂度：o(n)
    public static Node detectCycle(Node head) {
        HashSet<Node> set = new HashSet<>();
        Node q = head;
        while (q != null) {
            if (set.contains(q)) {
                return q;
            }
            set.add(q);
            q = q.next;
        }
        //无环返回空
        return null;
    }

    //法二：快慢指针
    //空间复杂度 o(1)
    //时间复杂度，会发现仅仅只是在上一段快慢指针代码的基础上走了a步
    /*最好情况：O(2a)
    最坏情况：O(2a+r)
    平均情况：O(2a+r/2)*/
    public static Node detectCycle2(Node head) {
        Node slow = head;
        Node fast = head;

        do {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        } while (slow != fast);

        //slow和fast相遇后
        // 将fast移动到开头
        fast = head;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        // fast == slow 再一次相遇
        return fast;
    }

}

············································································································································································································

3. 反转单链表（同LeetCode之反转链表）
   方法一：头插法
   

package com.cskaoyan.exercise;

/**
 * @author shihao
 * @create 2020-05-13 20:29
 */
public class Exercise03 {

    public static void main(String[] args) {
        Node head = new Node(3);
        head = new Node(2, head);
        head = new Node(1, head);
        print(head);

        head = reverse(head);
        print(head);
    }

	//法一：头插法
    public static Node reverse(Node head) {
        Node prev = null;
        Node cur = head;

        while (cur != null) {
            //保留下一个结点
            Node next = cur.next;

            //头插法
            cur.next = prev;
            prev = cur;

            cur = next;
        }
        return prev;
    }

    private static void print(Node head) {
        Node q = head;
        while (q != null) {
            System.out.print(q.value);
            if (q.next != null) {
                System.out.print(" ---> ");
            }
            q = q.next;
        }
        System.out.println();
    }
}

············································································································································································································

方法二：递归

使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。

//法二：递归
    public static Node reverse2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }

        Node ret = reverse2(head.next);
        head.next.next = head;
        //要不把head置为空的话，当递归到最后一个出口时，
        //head.next指向head的前一个结点，
        //而head的前一个结点的next指向head
        //这样就成环了，所以必须把head.next置为空
        head.next = null;
        return ret;
    }

············································································································································································································

作业：用 List 存储一些字符串，去除里面重复的字符串，只保留一个。