题目描述

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

 

解题思路：从头遍历整个链表，如果当前结点和下一结点值相同，则应当删除。为了保证结点不断，需要保存pre结点，然后找到不相等的next，pre->next = next;注意删除的是头结点的情况，单独处理。

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         if(pHead == NULL)15             return NULL;16         ListNode *pPreNode = NULL;17         ListNode *pNode = pHead;18         while(pNode != NULL)19         {20             ListNode *pNext = pNode->next;21             bool needDelete = false;22             if(pNext != NULL && pNext->val == pNode->val)23                 needDelete = true;24             if(!needDelete)//不等25             {26                 pPreNode = pNode;27                 pNode = pNode->next;28             }29             else//相等该删除30             {31                 int value = pNode->val;32                 ListNode *pToBeDel = pNode;33                 while(pToBeDel != NULL && pToBeDel->val == value)34                 {35                     pNext = pToBeDel->next;36                     delete pToBeDel;37                     pToBeDel = NULL;38                     pToBeDel = pNext;39                 }40                 if(pPreNode == NULL)//头结点被删除了41                     pHead = pNext;42                 else43                     pPreNode->next = pNext;44                 pNode = pNext;45  46             }47         }48         return pHead;49     }50 };