链表-重复值问题

场景1

链表升序有序，去掉链表中重复的节点
eg:
1->1->2->3->3->4->5->5
结果
1->2->3->4->5

思路

1. 每次判断尾指针和指针p的数据域是否相等，如果相等需要将指针p指向的节点删除，如图：

   
   
   

   删除后，重新赋值指针p的值，p = tail ->next

   
   

2. 如果尾指针的值和指针p的数据域不一致，则两根指针都想后移动一个节点，然后重复上面的动作继续判断，直至指针p指向NULL

   
   
   

   从上面的描述中，可以看出全程直涉及“中间尾删”，不涉及“头删”，所以头指针的一直没有发生变化，所以函数的返回值为NULL即可。当然，也可以原样不动的返回头指针的地址。

code

void delRepeatNode(ElemSN *head){
    if(head==NULL){
        return;
    }
    ElemSN *tail = head, *p = tail->next;
    while (p!=NULL) {
        if(tail->data==p->data){
            tail->next = p->next;
            free(p);
            p = tail->next;
        }else{
            tail = p;
            p=p->next;
        }
    }
}

场景2

链表升序有序，去掉含有重复值的节点。
eg:
1->1->1->3->4->5->6->6
去重后：
3->4->5
这个题比较烧脑

• 跟往常一样，使用两根指针q,p，如果发现这两个指针指向节点的数据域都是一样的，那么不仅要删除节点p,还要删除节点q，这意味着不仅p节点要有前驱指针，节点q也要有前驱指针，
• 这里使用tail代表节点q的前驱指针。起始情况下，tail和q指向同一个节点。
• 删除的节点可能是头结点，如本题需要删除的q节点即为头结点，所以要考虑头指针的指向是否需要变换。
• 什么时候删除节点q？因为如果和节点p同时进行删除的话，那么如果链表中存在奇数个相同的节点，如图，那么我们无法判断第三个节点是不是重复节点，所有，不能马上删除节点q，要等到节点q和指针p指向节点不一致时，才进行删除节点q。

具体步骤如下：

1. p,q节点的值相同，删除节点p

   
   

2. 标记节点q是重复节点

   
   

3. 继续删除节点p

   
   

4. 节点p的值和q的值不一致了，是时候删除节点q了，如果q节点是头节点，进行头删，并更新头指针的指向。

   
   

5. 没有重复的节点，指针整体向后移动

   
   

6. 没有发现重复节点，指针整体向后移动

   
   

7. 向后移动后，发现重复节点，但是需要删除的节点都是有前驱的，不虚！

   
   

code

ElemSN* delRepeatNode1(ElemSN *head){
    if (!head) {
        return NULL;
    }
    ElemSN *tail = head, *p = NULL, *q = NULL;
    p = head;
    while (p) {
        q = p;
        p = p->next;
        int flag = 0;
        while (p&&q->data == p->data) {
            flag = 1;
            q->next = p->next;
            free(p);
            p = q->next;
        }
        if (flag) {
            if (head == q) {
                head = head->next;
                if (head == tail->next) {
                    tail = head;
                }
            }
            else {
                tail->next = q->next;
            }
            free(q);
        }
        else {
            while (tail->next != p) {
                tail = tail->next;
            }
        }
    }
    return head;
}