算法之删除链表的重复的节点并返回头指针

 分析和思路：使用map保存每个节点的个数，大于1的个数链表不创建，其他的重新创建，这个方法的缺点是用了o（n）的空间。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 #include "iostream"
11 #include 

之前写的一个不用o（n）空间的，写的比较冗余，可读性比较差。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 
11 class Solution {
12 public:
13     ListNode* deleteDuplication(ListNode* pHead)
14     {
15         if (pHead == NULL)
16         {
17             return NULL;
18         }
19         bool flag = false;
20         ListNode* q = pHead;
21         bool find_flag = false;
22         ListNode* back = (ListNode*)malloc(sizeof(ListNode));
23 
24         
25         if( pHead->next!=NULL)
26         {
27             if (pHead->val == pHead->next->val)
28             {
29                 back = pHead;
30 
31                 flag = true;
32 
33             }
34             
35         }
36         else
37         {
38             return pHead; //只有一个节点
39         }
40         
41         while(q->next!=NULL)
42         {
43             
44             if (find_flag == true)
45             {
46                 back->next = q->next;
47                 q = back;
48                 find_flag = false;
49             }
50             
51             if (q->val != q->next->val)
52             {
53                 back = q;
54 
55                 q = q->next;
56                 continue;
57             }
58             else
59             {
60                 while(q->val == q->next->val&&q->next!=NULL)
61                 { 
62                     q->next = q->next->next;
63                 }
64                 
65                 find_flag = true;
66                 //free(q) 释放节点
67                 continue;
68             }
69         }
70         if (flag == true)
71         {
72             if(find_flag ==true)
73                 {
74                    back->next = q->next;
75                     q = back;
76                     return pHead->next;
77                     
78                 }
79             else 
80                 return pHead->next;
81         }
82         else
83         {
84             return pHead;
85         }
86     
87     }
88 };