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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if (!head || !head->next) {
        return head;
    }

    struct ListNode* pre = head;
    struct ListNode* cur = head->next;
    bool* flag = (bool* )malloc(sizeof(bool) * 3000);
    
    for(int i = 0;i < 3000;i++){
        flag[i] = false; //用数组实现哈希表来存放数据，标记需要删除的元素
    }

    while (cur) {

        while (pre->val == cur->val && cur) {
            cur = cur->next;
            flag[pre->val + 1000] = true;//使用移码的思想来实现对于负数的标记
        }

        pre->next = cur;//如果是一般情况那么这句代码就不起作用
        pre = cur;

        if (cur)
            cur = cur->next;

    }

    struct ListNode* pr = (struct ListNode* )malloc(sizeof(struct ListNode));
    pr->next = head;
    struct ListNode* tp = pr;
    struct ListNode* cr = head;

    while(cr){
        
        if(flag[cr->val + 1000]){
            tp->next = cr->next;
        }

        else{
            tp = cr;//不满足上述条件时才需要移动tp指针，否则就会讲tp指针指向一个本应该已被删除的元素
        }

        cr = cr->next;

    }

    return pr->next;

}