分析和思路:使用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 <map> 12 using namespace std; 13 //思路,先遍历整个链表,如果重复数量大于 1的都记录下来,然后再创建一个新的链表返回即可 14 15 16 17 18 19 class Solution { 20 public: 21 ListNode* deleteDuplication(ListNode* pHead) { 22 map<int, int> m; 23 if (pHead == NULL) 24 { 25 return NULL; 26 } 27 ListNode* temp = NULL; 28 temp = pHead; 29 while (temp != NULL) 30 { 31 m[temp->val] += 1; 32 temp = temp->next; 33 } 34 35 ListNode* pHeadBack = pHead; 36 temp = pHead; 37 while (temp!=NULL&&m[temp->val] > 1) 38 { 39 temp = temp->next; 40 } 41 if(temp==NULL) 42 { 43 return NULL; 44 } 45 pHeadBack = temp; 46 pHead = temp; 47 temp = temp->next; 48 ListNode* New; 49 while (temp != NULL) 50 { 51 if (m[temp->val] > 1) 52 { 53 temp = temp->next; 54 continue; 55 } 56 else 57 { 58 New = (ListNode*)malloc(sizeof(ListNode)); 59 New->val = temp->val; 60 New->next = NULL; 61 pHead->next = New; 62 New = New->next; 63 64 pHead = pHead->next; 65 temp = temp->next; 66 } 67 } 68 return pHeadBack; 69 70 } 71 };
之前写的一个不用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 };