【LC刷题系列】【持续更新】链表问题

141. 环形链表
判断链表是否存在环
暴力法：
一个指针在链表中步进，元素一个个添加到hashSet中，添加失败的时候 就是出现了重复节点的时候 返回true，因为HashSet有hash算法，所以时间复杂度是O(N)，但是空间复杂度是O(N)

    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            boolean neverShowUp = seen.add(head)
            if (!neverShowUp) {
                return true;
            }
            head = head.next;
        }
        return false;
    }

Floyd判圈法（快慢指针法）：
利用龟兔赛跑，如果存在环，快节点必定追上慢节点的原理，需要快节点每次步长为2，慢节点步长为1，相遇即是有环。

public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow!=fast){
            if(fast!=null&&fast.next!=null){
                fast = fast.next.next;
            }else{
                return false;
            }
            slow = slow.next;
        }
        return true;
    }

从这个Floyd判圈法可以延伸出来求环的起点的问题/求环长度的问题
环长度：快慢指针相遇后 快指针停止 记录当前位置，慢指针继续走，再次相遇即是环长度。
求环起点：数学问题，利用二者速度差，相遇后，快节点放回起点，两个节点相同速度继续走，会在环的起点处相遇。具体数学推导我也看迷糊啦。
求两个链表是否相交：把两个链表首尾相接，再用Floyd判断法，如果有环一定相交，如果无环一定平行。

203. 移除链表元素
用了递归的方法，这道题特殊的地方在于需要返回头结点，但是头结点有可能被移除，所以创建一个假的节点，把给定链表追在他后面，返回的时候直接返回假节点的next即可。

    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return head;
        }
        ListNode fakeNode = new ListNode(val+1);
        fakeNode.next = head;
        ListNode temp = fakeNode;
        while(temp.next!=null){
            if(temp.next.val==val){
                temp.next = temp.next.next;
            }else{
                temp = temp.next;
            }
        }
        return fakeNode.next;
    }