[数据结构与算法]【算法刷题】链表篇-删除链表中的重复节点

题目要求

删除链表中重复的结点__牛客网 (nowcoder.com)

思路：

• 如果链表为空或者 链表只有一个结点，直接返回链表的头结点

• 注意： 要定义三个指针

  • 
  • 初始：prev = NULL cur = Phead next = cur -> next

• 通过next指针遍历链表,注意：不是通过cur指针。next指针比cur指针更快到达NULL。next指针找和cur指向结点的值不相同的位置

• 如果找到了cur结点和next结点值不相等的位置 -> prev cur next 都迭代往后走，只有cur和next一起移动，prev才跟着移动

  • prev = cur;
    cur = next;
    next = next->next;
    

• 否则(cur结点和next结点值相等)： 让next一直往后走，直到找到next结点的值和cur结点值不相同的位置

  • while(cur -> val == next -> val)  //循环条件不完全正确，见下面情况case2
    {
        next = next -> next;//next一直往后走，直到找到和cur指向结点值不相同的位置
    }
    
    

  • 

    • 所以上述循环条件更改为：

    •   //注意要把next!=NULL条件放在前面，不然的话：next->val可能会对空指针解引用
      while(next!=NULL &&cur->val == next -> val )
      {
          next = next->next;
      }
      

  • 

  • 当出现cur->val 和next->val相同的情况，next一直循环往后走，直到next指向结点和cur指向结点的值不同，此时要判断prev是否为空。

    • 若prev为空 ->需要更改头指针的指向
    • 不为空 ->prev -> next 要指向next 防止造成野指针

• 若曾经出现next->val == cur->val 情况时：当next找到和cur指向结点不相同的结点后.释放从[cur , next)区间的结点

  • while(cur != next)
    {
        ListNode* del = cur;
        cur = cur->next;//保存下一个结点
        free(del);
    }
    

• 释放完成后，next指向cur的下一个结点，继续找重复结点

  • 注意：要判断next是否为空！否则会对空指针解引用

  • if(next != NULL) //也可以简写成if(next)
    {
        next = cur -> next;//next指向cur的下一个结点
    }
    //当next为空时,下一轮循环不再进入,这里也可以直接break跳出
    else
    {
        break;
    }
    

• 最后返回Phead头结点

总结：

• 定义三个指针,cur prev next，初始：prev = NULL cur = Phead next = Phead ->next
• 当next为空时，循环结束
• 如果cur->val != next ->val 三个指针一起移动
• 如果cur -> val == next -> val
  • next一直往后走,直到找到cur -> val != next->val 的位置 （注意：要防止next为空）
  • 找到了之后，要先判断此时的prev是否为空
    • 若prev为空：说明要更改头指针的指向
    • 若prev不为空：要更改prev的next的指向 prev->next = next;
  • 用cur遍历,释放[cur,next)区间的结点,释放完成后，cur 指向的时next位置
  • 判断此时next是否为空
    • 如果next ==NULL ：说明可以直接跳出循环了，break 也可以不写，通过下一次进入循环判断时结束
    • 如果next不为空：next指向cur的下一个结点。开启下一轮比较
• 最后返回Phead
• 
• 
• 

当所有结点都是重复的：

代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) 
    {
        //如果链表为空 /链表只有一个结点->直接返回头结点
        if(pHead == NULL || pHead ->next == NULL)
        {
            return pHead;
        }
        //定义三个指针
        ListNode* prev = NULL;
        ListNode* cur = pHead;
        ListNode* next = cur->next;
        //当next为空时，结束循环
        while(next)
        {
            //如果cur结点的值和next结点的值不同->三个指针一起往后走
            if(cur->val != next->val)
            {
                prev = cur;
                cur = next;
                next = next->next;
            }
            //不相同时：
            else
            {
                //找到cur结点的值和next结点的值不同的位置
                //要防止不为空
                while(next&& cur->val == next->val )
                {
                    //next一直往后走
                    next = next->next;
                }
                //判断prev是否为空
                //如果为空:说明要更换头指针的指向
                //不为空：修改prev的next指向，防止野指针
                if(prev)
                {
                    prev -> next = next;
                }
                else
                {
                    pHead = next;
                }
                //释放[cur,next)区间的结点	
                while(cur != next)
                {
                    ListNode* del = cur;
                    cur = cur->next ;//保存下一个结点，防止找不到
                    free(del);
                }
                //判断next是否为空：
                //若为空:说明可以直接跳出循环了，break  也可以不写，通过下一次进入循环判断时结束
                //不为空：next指向cur的下一个结点。开启下一轮比较
                if(next)
                {
                    next = cur->next;
                }
                /*
                else
                {
                    break;
                }
                */
            }
        }
         return pHead;
    }
};