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

本文主要是介绍算法之删除链表的重复的节点并返回头指针，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 分析和思路：使用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 };

这篇关于算法之删除链表的重复的节点并返回头指针的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！