首页 > 代码库 > leetcode - Remove Duplicates from Sorted List
leetcode - Remove Duplicates from Sorted List
题目：Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
个人思路：
1、删除链表的重复节点，先遍历一遍链表，统计不相同节点值的出现次数，这里借助map来统计
2、然后再遍历一遍链表，出现次数大于1的节点需要删掉，并且更新一下出现次数
3、注意一下头节点的删除和中间节点的删除就行了
代码：
1 #include <stddef.h> 2 #include <map> 3 4 using namespace std; 5 6 struct ListNode 7 { 8 int val; 9 ListNode *next;10 ListNode(int x) : val(x), next(NULL) {};11 };12 13 class Solution14 {15 public:16 ListNode *deleteDuplicates(ListNode *head)17 {18 map<int, int> total_count;19 20 //统计不相同节点值的出现次数21 for (ListNode *cur = head; cur != NULL; cur = cur->next)22 {23 map<int, int>::iterator it = total_count.find(cur->val);24 if (it != total_count.end())25 {26 total_count[cur->val] = it->second + 1;27 }28 else29 {30 total_count[cur->val] = 1;31 }32 }33 34 //删除重复节点35 for (ListNode *cur = head, *pre = head; cur != NULL; )36 {37 map<int, int>::iterator it = total_count.find(cur->val);38 39 //表明该节点重复40 if (it->second > 1)41 {42 total_count[cur->val] = it->second - 1;43 44 //删除头节点45 if (cur == head)46 {47 head = head->next;48 delete cur;49 cur = pre = head;50 }51 //删除中间节点52 else53 {54 pre->next = cur->next;55 delete cur;56 cur = pre->next;57 }58 }59 //节点不重复60 else61 {62 if (cur != head)63 {64 pre = pre->next;65 }66 67 cur = cur->next;68 }69 }70 71 return head;72 }73 };74 75 int main()76 {77 return 0;78 }
突然发现漏掉一个重要条件，链表已经排好序了，那么只需要判断当前节点与下一个节点是否相同就行了,如果相同则删除下一个节点，并且将当前节点和下下个节点连起来，如果不同就让当前节点指向下一个节点，哎，真是太傻比了。。。
代码：
1 #include <stddef.h> 2 #include <map> 3 4 using namespace std; 5 /* 6 struct ListNode 7 { 8 int val; 9 ListNode *next; 10 ListNode(int x) : val(x), next(NULL) {}; 11 }; 12 */ 13 class Solution 14 { 15 public: 16 ListNode *deleteDuplicates(ListNode *head) 17 { 18 /* 19 map<int, int> total_count; 20 21 //统计不相同节点值的出现次数 22 for (ListNode *cur = head; cur != NULL; cur = cur->next) 23 { 24 map<int, int>::iterator it = total_count.find(cur->val); 25 if (it != total_count.end()) 26 { 27 total_count[cur->val] = it->second + 1; 28 } 29 else 30 { 31 total_count[cur->val] = 1; 32 } 33 } 34 35 //删除重复节点 36 for (ListNode *cur = head, *pre = head; cur != NULL; ) 37 { 38 map<int, int>::iterator it = total_count.find(cur->val); 39 40 //表明该节点重复 41 if (it->second > 1) 42 { 43 total_count[cur->val] = it->second - 1; 44 45 //删除头节点 46 if (cur == head) 47 { 48 head = head->next; 49 delete cur; 50 cur = pre = head; 51 } 52 //删除中间节点 53 else 54 { 55 pre->next = cur->next; 56 delete cur; 57 cur = pre->next; 58 } 59 } 60 //节点不重复 61 else 62 { 63 if (cur != head) 64 { 65 pre = pre->next; 66 } 67 68 cur = cur->next; 69 } 70 } 71 72 return head; 73 */ 74 75 if (!head) 76 { 77 return NULL; 78 } 79 80 ListNode *cur = head; 81 ListNode *next = NULL; 82 83 while (cur->next) 84 { 85 next = cur->next; 86 if (cur->val == next->val) 87 { 88 cur->next = next->next; 89 delete next; 90 } 91 else 92 { 93 cur = cur->next; 94 } 95 } 96 97 return head; 98 } 99 };100 /*101 int main()102 {103 return 0;104 }105 */
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。