[数据结构与算法]链表-双指针-力扣705. 设计哈希集合

1. 题目

题目链接：705. 设计哈希集合

2. 思路

定义一个链表，初始化HashSet的时候就初始化一个头结点，然后先写contains函数，添加时先判断是否有数据，没有就直接添加在头结点后面，删除时先判断是否存在，存在就使用双指针删除。

3. 代码

class MyHashSet {

    /** Initialize your data structure here. */
    ListNode head;
    public MyHashSet() {
        head = new ListNode();
    }
    
    public void add(int key) {
        if (contains(key)) return;
        ListNode newNode = new ListNode(key);
        newNode.next = head.next;
        head.next = newNode;
    }
    
    public void remove(int key) {
        if (!contains(key)) return;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null) {
            if (fast.val == key) {
                slow.next = fast.next;
                break;
            }
            slow = slow.next;
            fast = fast.next;
        }
    }
    
    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        ListNode tmp = head.next;
        while (tmp != null) {
            if (tmp.val == key) return true;
            else tmp = tmp.next;
        }
        return false;
    }
}

class ListNode {
    public int val;
    public ListNode next;
    public ListNode() {}
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}