【算法刷题】链表篇-删除链表中的重复节点

文章目录

• • • 题目要求
    • 思路：
    • 代码：

题目要求

删除链表中重复的结点__牛客网 (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;    }};