剑指offer-删除链表中重复的结点

描述

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

求解思路

遍历两个相邻的节点，如果相等，就继续向后删除值相同的节点。
删除重复节点前，需要一个节点来记录重复节点前的前缀节点。
由于在删除重复节点时，前缀节点可能并不存在，这时候需要分两种情况分析，比较绕。

 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==nullptr || pHead->next==nullptr){
15             return pHead;
16         }
17         ListNode* fp=pHead,*rp=pHead;  // 删除流程的前后节点
18         ListNode* nH=nullptr,*nR=nullptr;   // 不好记录重复节点的前节点，用新的链表
19         bool hNode=true;
20         // 如果一个节点的next等于next的next，开始清除
21         while(rp!=nullptr && rp->next!=nullptr){
22             if(rp->next->val==rp->val){  // 如果fp后面的两个节点相同，就准备删除了
23                 int nv=rp->val;
24                 while(rp!=nullptr &&　rp->val==nv){
25                     ListNode* tp=rp;
26                     rp=rp->next;
27                     delete tp;
28                 }
29                 if(hNode){
30                     fp=rp;pHead=rp;
31                 }else{
32                     fp->next=rp;
33                 }
34             }else{
35                 if(hNode){ // 当有前缀节点时，需要记录前缀节点，fp不能++
36                     pHead=rp;rp=rp->next;
37                     hNode=false;
38                 }else{
39                     fp=fp->next;rp=rp->next;
40                 }
41             }
42         }
43         return pHead;
44     }
45 };

　　改进：在原始链表前加一个节点(-1)。

 1 class Solution {
 2 public:
 3     ListNode* deleteDuplication(ListNode* pHead)
 4     {
 5         ListNode *vhead = new ListNode(-1);
 6         vhead->next = pHead;
 7         ListNode *pre = vhead, *cur = pHead;       
 8         while (cur) {
 9             if (cur->next && cur->val == cur->next->val) {
10                 cur = cur->next;
11                 while (cur->next && cur->val == cur->next->val) {
12                     cur = cur->next;
13                 }
14                 cur = cur->next;
15                 pre->next = cur;
16             }
17             else {
18                 pre = cur;
19                 cur = cur->next;
20             }
21         }
22         return vhead->next;
23     }
24 };

心之所愿，永不相忘