算法 Day2

删除无序链表中的重复节点，保留一个

给定一个无序单向链表的头节点，删除内部的重复节点，使其内部节点元素不重复。（值相等即认为重复）

解法一 使用Map数据结构，以空间换时间

使用Map数据结构，遍历链表，以链表节点为key，节点出现次数为value,在存储次数时，仅第一次出现时把value置为1，后续进入如果已经发现Map中存储的次数为1，那么直接把该节点删除。额外需要注意的时，利用Hash类的数据结构时，我们应该重写equals和hashcode方法，用内部的value作为判断标准。
考虑到是不重复的节点及Map数据结构，同时我们只需要判断节点是不是在集合中，也就是并不需要真正存储次数，而HashSet内部是通过HashMap来实现的，因此可以选择使用HashSet。

static void removeRepeatNode(LinkNode head){
    if(head != null){
        HashSet<LinkNode> hashSet = new HashSet<>();
        LinkNode pre = head;
        LinkNode cur = head.mNext;
        //由于当前节点从头节点下一个开始，因此记录第一个节点的值
        hashSet.add(pre);
        while(cur != null){
                if(hashSet.contains(cur)){
                    // 需要移除
                    cur = cur.mNext;
                    pre.mNext = cur;
                }else{
                    pre = cur;
                    // 如果没有这个节点，那么需要添加该节点
                    hashSet.add(cur);
                    cur = cur.mNext;
                }
        }
    }
}

static class LinkNode{
    int mValue;
    LinkNode mNext;

    public LinkNode(int value) {
        mValue = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof LinkNode)) return false;

        LinkNode linkNode = (LinkNode) o;

        return mValue == linkNode.mValue;
    }

    @Override
    public int hashCode() {
        return mValue;
    }
}

容易出错处：

1）节点需要重写equals和hashcode方法

2）添加未出现过的节点时需要先添加后设置cur为下一个节点

复杂度分析：
需要遍历一遍单向链表，因此时间复杂度O(n);空间复杂度上需要依赖一个Map数据结构，因此空间复杂度O(n)

解法二： 不使用额外的空间复杂度

从头到尾部遍历链表，每次遍历到一个节点，和后面所有的节点比较，如果两个节点值相等，那么把被比较的节点删除。

private static void removeRepeatNode2(LinkNode head){
    while(head != null){
        //遍历后续所有节点
        LinkNode cur = head.mNext;
        LinkNode pre = head;
        while(cur != null){
            if(cur.mValue == head.mValue){// pre不变
                pre.mNext = cur.mNext;
                cur = cur.mNext;
            }else{//pre需要跟着变
               pre = cur;
               cur = cur.mNext;
            }
        }
        //继续下一个节点
        head = head.mNext;
    }
}

复杂度分析：
需要遍历整个链表中每个节点，在遍历到每个节点的同时，需要拿该节点后面所有的元素跟它比较，因此时间复杂度是O(n^2)，空间复杂度O(1)

代码

地址