编码实现从无序链表中移除重复项(C和JAVA实例)
如果不能使用临时缓存,你怎么编码实现? 复制代码 代码如下: 方法一:不使用额外的存储空间,直接在原始链表上进行操作。首先用一个指针指向链表头节点开始,然后遍历其后面的节点,将与该指针所指节点数据相同的节点删除。然后将该指针后移一位,继续上述操作。直到该指针移到链表。 void delete_duplicate1(node* head){ 方法二:如果允许使用额外的空间,则能通过空间换时间,来降低算法的复制度。可以使用hash表来完成,既然是面试题,我们这里可以暂时先不考虑使用hash可能带来的一些问题,先假设它是完美的。即假设它能将任意整数hash到一定范围,不会出现负数下标,不会出现hash冲突等。 复制代码 代码如下: void delete_duplicate2(node* head) { node*p=head->next; node*q=p->next; memset(hash,sizeof(hash)); hash[p->data]=1;//置为1,表示该数已经出现过 while(q!=NULL){ if(hash[q->data]!=0){ node*pDel=q; p->next=q->next; q=p->next; free(pDel); } else{ hash[q->data]=1;//置为1,表示该数已经出现过 p=q; q=q->next; } } } JAVA参考代码: 复制代码 代码如下: public static void deleteDups(LinkedListNode n) { Hashtable table = new Hashtable(); LinkedListNode previous = null; while (n != null) { if (table.containsKey(n.data)) previous.next = n.next; else { table.put(n.data,true); previous = n; } n = n.next; } } public static void deleteDups2(LinkedListNode head) { if (head == null) return; LinkedListNode previous = head; LinkedListNode current = previous.next; while (current != null) { LinkedListNode runner = head; while (runner != current) { // Check for earlier dups if (runner.data == current.data) { LinkedListNode tmp = current.next; // remove current previous.next = tmp; current = tmp; // update current to next node break; // all other dups have already been removed } runner = runner.next; } if (runner == current) { // current not updated - update now previous = current; current = current.next; } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |