题解 | #删除有序链表中重复的元素-II#

注释已经详细给出了 时间复杂度O(n) 空间复杂度O(1)

补充：无序时使用哈希表统计各数值出现次数，仅保留出现次数为1的结点

对比：算法比官方复杂一点，但是考虑到了内存泄漏的问题，面试时可以询问是否删除结点依次选择算法

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
      if (head == nullptr || head->next == nullptr) {
        return head;
      }
      
      // 首元结点可以解决第一个元素就是重复的情况
      ListNode *head_node = new ListNode(-1);
      head_node->next = head;
      
      // 三个结点：pre指向的结点绝对不会和cur重复，cur和nex用来删除重复结点
      ListNode *pre = head_node, *cur = head, *nex = head->next;
      
      while (nex) {
          // 不重复则整体往前挪动，一次只能挪动一格，防止nex和nex->是重复元素
        if (cur->val != nex->val) {
          pre = cur;
          cur = nex;
          nex = nex->next;
        } else {
          // 重复有两种情况：只有两个重复 | 有多个重复
          // 重复则找出这个重复子链表，不断删除直到剩下两个重复元素
          while (nex->next && nex->next->val == cur->val) {
            nex = nex->next;
          }
          while (cur->next != nex) {
            ListNode *tmp = cur;
            cur = cur->next;
            delete(tmp);
          }
          // 两个while处理后，只剩下两个重复元素这一种情况
          pre->next = nex->next;
          delete(cur);
          delete(nex);
          // 考虑最后两个元素重复的情况
          if (pre->next == nullptr) {
            break;
          }
          // 移动指针
          cur = pre->next;
          nex = cur->next;
        }
      }
      
      head = head_node->next;
      delete(head_node);
      
      return head;
    }
};