题解 | #删除链表中重复的结点#复杂度O(N)和O(1)

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplication(struct ListNode* pHead ) {
    //哨兵位
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = pHead;
    guard->val = -1;
    //三指针依次前进遍历链表
    struct ListNode* n1 = pHead, *n2 = guard, *n3 = guard;
    while(n1)
    {
        //值不相同，三指针前进
        if(n1->val != n2 ->val)
        {
            n3 = n2;
            n2 = n1;
            n1 = n1->next;
        }
        //值相同
        else 
        {
            //del存储将要free节点的地址
            struct ListNode* del =  NULL;
            //n2节点不动 n1节点前进，顺便free
            while(n1->val == n2->val && n1)
            {
                del = n1;
                n1 = n1->next;
                n2->next = n1;
                free(del);
            }
            //出循环后删除n2，并链接链表
            del = n2;
            n2 = n1;
            if(guard->next == del)//如果链表被free，及时更新链表头
                pHead = n2;
            free(del);
            n3->next = n2;
            if(n1)//如果n1不为空，n1继续前进，为空就不操作
                n1 = n1->next;
        }        
    }
        free(guard);//释放哨兵位
        return pHead;
 
}