题目的主要信息:

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

方法一:

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

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。