1.首先加上一个空的头结点,便于处理删除第一个结点的情况。
2.需要设一个pre指针跟踪工作结点及记录一路留下来的结点。
3.用2个指针p,q来比较结点值是否相同。
4.不同时,pre指向p,p指向q,q指向q->next。
5.相同时,继续看q的后面是否还有一样,直到找到不同的,或者到链尾。
a,若后面还有不同的,则更换pre,p,q指针的指向,继续比较。
b,若q值后面一直到链尾没有不同的,那么从p到q都要删掉,pre指空完结。
struct ListNode* deleteDuplicates(struct ListNode* head ) { struct ListNode* L =(struct ListNode*)malloc(sizeof(struct ListNode)); //新建结点 L->next = head; //指针域置空 if(head == NULL || head->next == NULL) return head; //0个或1个元素时不会有重复的元素,原样返回即可 struct ListNode* pre = L; //前驱指针 struct ListNode* p = head; struct ListNode* q = head->next; while(q != NULL){ if(q->val != p->val){ //不同值时均后移 pre = p; p = q; q = q->next; } else{ while(q->next->val == q->val && q->next != NULL) q = q->next; //后面还有相同值时继续后移 if(q->next == NULL){ //竟然一直移到了末尾 pre->next = NULL; //从p到q全部不要 return L->next; //提前返回 } p = q->next; //略过重复元素,重新开始比较 pre->next = p; //前驱也要同步跟上 q = p->next; } } return L->next; }