LeetCode | Remove Duplicates from Sorted List

发布时间:2016-12-8 16:03:03 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"LeetCode | Remove Duplicates from Sorted List",主要涉及到LeetCode | Remove Duplicates from Sorted List方面的内容,对于LeetCode | 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:遍历的时候,利用Hash表保存已经遍历的数值。对于每个数值,我们先查看Hash表中是否已经存在这个值,若存在,链表跳过该节点;若不存在,输出结果保留该节点。为了节省空间,我们更可以用bitmap来实现,当时bitmap需要同时支持正数与负数。 思路2:由于链表已经排序,我们可以直接遍历整个链表来移除重复的结点。 代码: 思路1: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class bitmap { public: bitmap(int n);~bitmap(); void set(int k); bool val(int k); private: int len; unsigned int * map; unsigned int * reversemap; bool zero; }; bitmap: :bitmap(int n) { len = n / 32 + 1; map = new unsigned int[len]; reversemap = new unsigned int[len]; for (int i = 0; i < len; i++) { map[i] = 0; reversemap[i] = 0; zero = false; } } void bitmap: :set(int k) { bool reverse = true; if (k == 0) { zero = true; } else if (k < 0) { reverse = false; k = -k; } int a = k / 32; int b = k % 32; if (a >= len) { return; } else { if (reverse) { int tmp = reversemap[a] / pow(2, b); if (tmp % 2 == 0) { reversemap[a] += pow(2, b); } } else { int tmp = map[a] / pow(2, b); if (tmp % 2 == 0) { map[a] += pow(2, b); } } } } bool bitmap: :val(int k) { bool reverse = true; if (k == 0) { return zero; } else if (k < 0) { reverse = false; k = -k; } int a = k / 32; int b = k % 32; if (a >= len) { return false; } else { if (reverse) { int tmp = reversemap[a] / pow(2, b); if (tmp % 2 == 1) { return true; } else { return false; } } else { int tmp = map[a] / pow(2, b); if (tmp % 2 == 1) { return true; } else { return false; } } } } class Solution { public: ListNode *deleteDuplicates(ListNode *head) { // Start typing your C/C++ solution below // DO NOT write int main() function bitmap* bm = new bitmap(32767); if(head == NULL) { return NULL; } ListNode * p = head; ListNode * begin = p; bm->set(p->val); while(p->next != NULL) { if(bm->val(p->next->val)) { ListNode * t = p->next->next; p->next = t; } else { bm->set(p->next->val); p = p->next; } }; return begin; } }; 思路2: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if(head == NULL || head->next ==NULL) return head; else { ListNode * pre = head; ListNode * cur = head->next; while(pre!=NULL&&cur!=NULL) { if(pre->val == cur->val) { pre->next=cur->next; cur=cur->next; } else { pre=pre->next; cur=cur->next; } }; return head; } } };

上一篇:百练 2696 计算表达式的值
下一篇:C语言 判断是否素数

相关文章

相关评论