题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表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;
        }

C++ 代码如下：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        map<int,int> maps;
        if (pHead != NULL) {
            // 遍历添加到set中
            while (pHead != NULL) {
                if (!maps.count(pHead->val)>0) {
                    maps[pHead->val]=1;
                }else{
                    maps[pHead->val]=-1;
                }
                pHead = pHead->next;
            }
            ListNode* listNode = new ListNode(-1);
            ListNode* temp = listNode;
            map<int, int>::iterator iter;
            iter = maps.begin();
            while(iter!=maps.end()){
                if(iter->second==1){
                    temp->next = new ListNode(iter->first);
                    temp = temp->next;
                }
                iter++;
            }
            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;
    }

C++ 代码如下：

class Solution {
public:
    ListNode *deleteDuplication(ListNode *pHead) {
        ListNode *head = new ListNode(-1);
        head->next = pHead;
        // 上一个元素指针为pre
        ListNode *pre = head;
        ListNode *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)，只遍历了一次链表。