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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
struct ListNode* deleteDuplicates(struct ListNode* head ) {
    // write code here
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* phead = NULL;     //临时的头指针
    struct ListNode* tail = head;      //遍历的最快的指针
    struct ListNode* tmp = NULL;       //判断是和tail否是相同元素
    struct ListNode* bottom = NULL;     //新链表的尾指针
    tmp = tail;
    tail = tail->next;
    
    while(tail != NULL)
    {
        if (tmp->val == tail->val)
        {
            //值相等
            while(tail != NULL )
            {
                if (tmp->val != tail->val)
                {
                    tmp = tail;
                    tail = tail->next;
                    if (phead == NULL && tail == NULL)
                    {
                        phead = bottom = tmp;
                    }
                    break;
                }
                tail = tail->next;
            }
            
        }
        else 
        {
            //值不同
            if (phead == NULL)
            {
                phead = bottom = tmp;
            }
            else 
            {
                bottom->next = tmp;
                bottom = tmp;
            }
            tmp = tail;
            tail = tail->next;
        }
    }
    //注意因为上面的循环会漏掉最后一个所以在下面再判断一次
    
    if (bottom != NULL)
    {    
        if (tmp->next == NULL && tmp->val != bottom->val)
        {
            bottom->next = tmp;
            bottom = tmp;
        }
        bottom->next = NULL;
    }
    head = phead;
    return head;
}