【剑指offer】删除链表中重复的节点，C++实现（链表）

0.简介

本文是牛客网《剑指offer》笔记。

1.题目

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

2.思路

      链表有0个节点

      链表有1个节点

      链表有2个以上节点

三个指针和两层循环实现删除链表中重复的节点。

首先，检查边界条件（链表有0个节点或链表有1个节点）时，返回头结点；其次，避免由于第一个节点是重复节点而被删除，新建一个指向头结点的节点；再次，建立三个指针pre/p/next，分别指向当前节点的前序节点、当前节点、当前节点的后续节点；最后循环遍历整个链表，如果节点p的值和节点next的值相同，则删除节点p和节点next，pre和下一个没有重复的节点连接。如果节点p的值和节点next的值不同，则三个指针向后移动一个指针。

3.code

  1 /*
  2 struct ListNode {
  3     int val;
  4     struct ListNode *next;
  5     ListNode(int x) :
  6         val(x), next(NULL) {
  7     }
  8 };
  9 */
 10 class Solution {
 11 public:
 12     ListNode* deleteDuplication(ListNode* pHead)
 13     {
 14           // 链表有0个/1个节点，返回第一个节点
 15           if(pHead==NULL||pHead->next==NULL)
 16               return pHead;
 17           else
 18           {
 19               // 新建一个头节点，防止第一个结点被删除
 20               ListNode* newHead=new ListNode(-1);
 21               newHead->next=pHead;
 22 
 23               // 建立索引指针
 24               ListNode* p=pHead;      // 当前节点
 25               ListNode* pre=newHead;  // 当前节点的前序节点
 26               ListNode* next=p->next;    // 当前节点的后序节点
 27 
 28               // 从头到尾遍历编标
 29               while(p!=NULL && p->next!=NULL)
 30               {
 31                   if(p->val==next->val)//如果当前节点的值和下一个节点的值相等
 32                   {
 33                       // 循环查找，找到与当前节点不同的节点
 34                       while(next!=NULL && next->val==p->val)
 35                       {
 36                           ListNode* temp=next;
 37                           next=next->next;
 38 
 39                           // 删除内存中的重复节点
 40                           delete temp;
 41                           temp = nullptr;
 42 
 43                       }
 44 
 45                     pre->next=next;
 46                     p=next;
 47                   }
 48                   else//如果当前节点和下一个节点值不等，则向后移动一位
 49                   {
 50                       pre=p;
 51                       p=p->next;
 52                   }
 53                   next=p->next;
 54               }
 55            return newHead->next;//返回头结点的下一个节点
 56           }
 57     }
 58 };