剑指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 -