剑指offer（五十六）：删除链表中重复结点

刷题平台：牛客网

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

题目分析：

题目难点在于要把所有重复的结点都删除，即1->1->1->1->1->1->1处理后应为{}

方法一：每次都删除重复的两个，记录上一次删除的值，如果当前值等于上一次删除的值(即出现奇数个重复结点)则继续删除当前结点，否则，结点依次向下走。

方法二：当当前结点值与后面一个结点的值相等时，应循环删除后面一个与当前结点值相等的结点，最后删除当前结点，由于要删除当前结点，因此需要有一个前向指针来指向当前结点的上一个结点，

解题过程中需要注意的是可能存在PHead被删除的情况，所以要对PHead进行处理，还有避免出现NULL->next的情况

题目实现：

C++实现方法一：

class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(!pHead) return NULL;
        //设置三个指针 
        ListNode * pre = new ListNode(-1);  //当前指针的前一个指针
        pre->next = pHead;
        ListNode * p = pHead;   //当前指针
        ListNode * pNext = p->next;  //当前指针的后一个指针
        int deleteVal = -2147483648;
        while(pNext){
            //重复 
            if(p->val == pNext->val){
                deleteVal = p->val;  //保留要删除的重复结点的值 
                pre->next = pNext->next;   //修改指针 
                ListNode * tmp1  = pNext;   //将重复的两个节点都删除
                ListNode * tmp2 = p;
                p = pre->next;
　　　　　　　　　　//判断，防止出现NULL->next的情况
                if(p)
                    pNext = p->next;
                else
                    pNext = NULL;
　　　　　　　　　　//处理头结点，防止出现头结点被删除的情况
                if(tmp2 == pHead){
                    pHead = p;
                } 
                delete tmp1;
                delete tmp2;
            }
            else if(p->val == deleteVal){//如果存在奇数个重复结点，将剩下的一个结点删除
                
                pre->next = p->next;
                ListNode * tmp  = p;
                
                p = p->next;
                pNext = p->next;
                if(tmp == pHead)
                    pHead = p;
                delete tmp;
            }
            else{
                pre = p;
                p = p->next;
                pNext = p->next;
            }
        }
        if(p&&p->val == deleteVal){
          delete p;
          return NULL;
        }
        return pHead;
    }
}；

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null)   return null;
        ListNode pre = new ListNode(-1);//设置一个前向指针指向工作结点的下一个结点
        pre.next = pHead;
        ListNode p = pHead;//工作结点
        boolean flag = false;//用来标记是否进行了删除操作
        while(p!=null){
            //当出现重复时，循环删除后面的结点
            while(p.next != null && p.val == p.next.val){
                p.next = p.next.next;
                flag = true;
            }
　　　　　　　//上一步进行了删除，那么应该把当前结点也删掉
            if(flag){
                if(pHead == p)
                    pHead = p.next;
                pre.next = p.next;
                p = p.next;
                
            }else{
                pre = p;
                p = p.next;
            }
            flag = false;
        }
        return pHead;
    }
}