劍指Offer（五十六）-- 删除連結清單中重複的元素

Github倉庫位址：https://github.com/Damaer/CodeSolution

筆記位址：https://damaer.github.io/CodeSolution/

倉庫介紹：刷題倉庫：CodeSolution

題目描述

在一個排序的連結清單中，存在重複的結點，請删除該連結清單中重複的結點，重複的結點不保留，傳回連結清單頭指針。例如，連結清單

1->2->3->3->4->4->5

處理後為

1->2->5

示例1

輸入

{1,2,3,3,4,4,5}

傳回值

{1,2,5}

節點的資料結構如下：

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
           

複制

思路以及解答

第一種做法是借助額外的空間，使用了LinkedHashMap,先周遊一次，将裡面的元素以及出現的次數，記錄下來，key是出現的元素，value是出現的次數，隻要出現超過一次，就将其value置為-1。

再次周遊LinkedHashMap裡面的元素，取出value不為-1的元素，也就是出現一次的元素，拼接成為連結清單。實作代碼如下：

public ListNode deleteDuplication(ListNode pHead) {
            HashMap<Integer,Integer> maps = new LinkedHashMap<>();
            if (pHead != null) {
                // 周遊添加到set中
                while (pHead != null) {
                    if (!maps.containsKey(pHead.val)) {
                        maps.put(pHead.val,1);
                    }else{
                        maps.put(pHead.val,-1);
                    }
                    pHead = pHead.next;
                }
                ListNode listNode = new ListNode(-1);
                ListNode temp = listNode;
                for (Map.Entry<Integer,Integer> entry: maps.entrySet()) {
                    if(entry.getValue()==1){
                        temp.next = new ListNode(entry.getKey());
                        temp = temp.next;
                    }
                }
                return listNode.next;
            }
            return null;
        }
           

複制

上面的做法借助了額外的空間，空間複雜度為O(n)，時間複雜度為O(2n)，也就是O(n)。

當然，還有另外一種做法，就是不需要借助額外的空間，也就是原地删除，對比前後兩個元素，如果相同的情況下，接着周遊後面的元素，直到元素不相等的時候，将前面的指針指向最後一個相同的元素的後面，相當于跳過了相同的元素。

public ListNode deleteDuplication(ListNode pHead) {
        ListNode head = new ListNode(-1);
        head.next = pHead;
        // 上一個元素指針為pre
        ListNode pre = head, cur = pHead;
        while (cur!=null) {
            if (cur.next!=null && cur.val == cur.next.val) {
                cur = cur.next;
                while (cur.next!=null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
                pre.next = cur;
            }
            else {
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }

           

複制

空間複雜度為O(1)，沒有借助額外的空間，時間複雜度為O(n)，隻周遊了一次連結清單。

【作者簡介】：

秦懷，公衆号【秦懷雜貨店】作者，技術之路不在一時，山高水長，縱使緩慢，馳而不息。個人寫作方向：Java源碼解析，JDBC，Mybatis，Spring，redis，分布式，劍指Offer，LeetCode等，認真寫好每一篇文章，不喜歡标題黨，不喜歡花裡胡哨，大多寫系列文章，不能保證我寫的都完全正确，但是我保證所寫的均經過實踐或者查找資料。遺漏或者錯誤之處，還望指正。

平日時間寶貴，隻能使用晚上以及周末時間學習寫作

- END -