题目的主要信息：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

方法一：

用两个指针遍历一遍链表，pre和cur指针。遍历一遍链表，若当前结点cur的值和下一结点相同，表示有重复结点，用一个循环找到当前所有的重复结点的末尾，将pre结点跳连接到下一个不重复的结点上；如果当前结点不是重复结点，则直接往下遍历。 具体做法：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
         ListNode *newHead = new ListNode(-1);
         newHead->next = pHead;
         ListNode *pre = newHead, *cur = pHead;
         while (cur) {//遍历一遍链表
            if (cur->next && cur->val == cur->next->val) {//删除重复结点
                while (cur->next && cur->val == cur->next->val) {//循环找到重复的节点
                    cur = cur->next;
                }
                cur = cur->next;
                pre->next = cur;//跳过重复节点连接
            }else {//如果不是重复结点，直接往下遍历
                pre = cur;
                cur = cur->next;
            }
        }
        return newHead->next;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历一遍链表。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。

方法二：

遍历一遍链表，建立结点值和个数的映射，保存在mp中。在当前链表前加上一个新的头节点newHead，便于遍历，然后从newHead开始再遍历一遍链表，每遍历一个结点查询它出现的次数，如果是重复的结点就重设连接跳过它，如果不是重复的结点就继续往下遍历。

具体做法：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if(pHead == NULL){
            return NULL;
        }
        ListNode *newHead = new ListNode(-1);
        newHead->next = pHead;
        ListNode *cur = newHead;
        unordered_map<int, int> mp;//用于保存结点个数
        while (cur) {//统计每个结点的个数
            mp[cur->val]++;
            cur = cur->next;
        }
        cur = newHead;
        while (cur->next) {//遍历一遍链表
            if(mp[cur->next->val] != 1){
                cur->next = cur->next->next;//跳过重复结点
            }else{
                cur = cur->next;//往下遍历
            }
        }
        return newHead->next;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历一遍链表。
• 空间复杂度：$O(n)O(n)$，mp需要建立结点值和个数的映射，最坏情况下mp的大小为n。