算法 Day2

刪除無序鏈表中的重復(fù)節(jié)點(diǎn)，保留一個

給定一個無序單向鏈表的頭節(jié)點(diǎn)，刪除內(nèi)部的重復(fù)節(jié)點(diǎn)，使其內(nèi)部節(jié)點(diǎn)元素不重復(fù)。（值相等即認(rèn)為重復(fù)）

解法一 使用Map數(shù)據(jù)結(jié)構(gòu)，以空間換時間

使用Map數(shù)據(jù)結(jié)構(gòu)，遍歷鏈表，以鏈表節(jié)點(diǎn)為key，節(jié)點(diǎn)出現(xiàn)次數(shù)為value,在存儲次數(shù)時，僅第一次出現(xiàn)時把value置為1，后續(xù)進(jìn)入如果已經(jīng)發(fā)現(xiàn)Map中存儲的次數(shù)為1，那么直接把該節(jié)點(diǎn)刪除。額外需要注意的時，利用Hash類的數(shù)據(jù)結(jié)構(gòu)時，我們應(yīng)該重寫equals和hashcode方法，用內(nèi)部的value作為判斷標(biāo)準(zhǔn)。
考慮到是不重復(fù)的節(jié)點(diǎn)及Map數(shù)據(jù)結(jié)構(gòu)，同時我們只需要判斷節(jié)點(diǎn)是不是在集合中，也就是并不需要真正存儲次數(shù)，而HashSet內(nèi)部是通過HashMap來實(shí)現(xiàn)的，因此可以選擇使用HashSet。

static void removeRepeatNode(LinkNode head){
    if(head != null){
        HashSet<LinkNode> hashSet = new HashSet<>();
        LinkNode pre = head;
        LinkNode cur = head.mNext;
        //由于當(dāng)前節(jié)點(diǎn)從頭節(jié)點(diǎn)下一個開始，因此記錄第一個節(jié)點(diǎn)的值
        hashSet.add(pre);
        while(cur != null){
                if(hashSet.contains(cur)){
                    // 需要移除
                    cur = cur.mNext;
                    pre.mNext = cur;
                }else{
                    pre = cur;
                    // 如果沒有這個節(jié)點(diǎn)，那么需要添加該節(jié)點(diǎn)
                    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）節(jié)點(diǎn)需要重寫equals和hashcode方法

2）添加未出現(xiàn)過的節(jié)點(diǎn)時需要先添加后設(shè)置cur為下一個節(jié)點(diǎn)

復(fù)雜度分析：
需要遍歷一遍單向鏈表，因此時間復(fù)雜度O(n);空間復(fù)雜度上需要依賴一個Map數(shù)據(jù)結(jié)構(gòu)，因此空間復(fù)雜度O(n)

解法二： 不使用額外的空間復(fù)雜度

從頭到尾部遍歷鏈表，每次遍歷到一個節(jié)點(diǎn)，和后面所有的節(jié)點(diǎn)比較，如果兩個節(jié)點(diǎn)值相等，那么把被比較的節(jié)點(diǎn)刪除。

private static void removeRepeatNode2(LinkNode head){
    while(head != null){
        //遍歷后續(xù)所有節(jié)點(diǎn)
        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;
            }
        }
        //繼續(xù)下一個節(jié)點(diǎn)
        head = head.mNext;
    }
}

復(fù)雜度分析：
需要遍歷整個鏈表中每個節(jié)點(diǎn)，在遍歷到每個節(jié)點(diǎn)的同時，需要拿該節(jié)點(diǎn)后面所有的元素跟它比較，因此時間復(fù)雜度是O(n^2)，空間復(fù)雜度O(1)

代碼

地址