LeetCode.82 删除排序链表中的重复元素 二

LeetCode.82 删除排序链表中的重复元素 二
题目

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
   
    if(head == NULL) return head;
    struct ListNode* _head = malloc(sizeof(struct ListNode));
    _head->next = head;  //头结点
    struct ListNode* r = _head,*p = _head->next,*q = _head->next->next;
    while(q != NULL)
    {
   
        if(p->val == q->val)
        {
   
            while(q!=NULL && p->val == q->val) 
            {
   
                
                 q = q->next;
                 
            }
           //printf("%d  %d\n",r->val,q->val);
            r->next = q; //删除
            p = q;
            if(q!=NULL)
            q = q->next;
        }
        else
        {
   
            r = r->next;
            p = p->next;
            q = q->next;

        }
    }
    if(r == _head)
    {
   
        return r->next;
    }
    else
    {
   
        return _head->next;
    }
}

思路:
1，提供的是无空头链表,需要加一个头结点来统一操作
2，使用三个工作指针
r：记录前一个节点，方便删除操作
p：记录此基准节点
q：前进节点
两种情况：
一 如果p与q不同，则p，q，r，均前进；
二 如果p与q相同，则q前进，直到与p不同，此时删除r与q之间的节点即可。

返回时注意，如果r始终未移动，说明相同节点均在前半部分，返回 r->next，
否则，返回原 head。

总结：此类题原理不难，要小心细节，比如加头结点、注意next越界操作，还有不要吝啬声明变量，重复使用next可能会把自己绕晕。