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;
}

京公网安备 11010502036488号